二叉树合集(一)——二叉树的创建、遍历、判断两棵树相等、叶子节点数量。
作者:
三行四列行列式
,
2022-11-22 11:59:27
,
所有人可见
,
阅读 217
#include<iostream>
using namespace std;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//创建二叉树
bool InitBiTree(BiTree &T){
char ch;
cin>>ch;
if(ch == '#'){
T=NULL;
}else{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void visit(BiTNode *p){
cout<<p->data<<" ";
}
void PreOrder(BiTree T){
if(T == NULL) return ;
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
void InOrder(BiTree T){
if(T == NULL ) return ;
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
void PostOrder(BiTree T){
if(T == NULL) return ;
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
//统计叶子节点的数量
int CountLeaf(BiTree T,int &count){
if(T!=NULL&&T->lchild==NULL&&T->rchild==NULL){
count++;
}
else{
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
return count;
}
//判断两棵树是否相等
//按照先序顺序一一比较节点,若有异常直接结束递归
int CmpTree(BiTree T1,BiTree T2){
//都是空树
if(T1==NULL&&T2==NULL) return 1;
//有一个结点为空,另一个不是空
if(T1==NULL||T2==NULL) return 0;
//值不等
if(T1->data!=T2->data) return 0;
//左右子树都是1才表示相等
return CmpTree(T1->lchild,T2->lchild) && CmpTree(T1->rchild,T2->rchild);
}
int main()
{
int count=0;
BiTree T1=(BiTree)malloc(sizeof(BiTree));
BiTree T2=(BiTree)malloc(sizeof(BiTree));
//输入样例:ABD##E##C##
InitBiTree(T1),InitBiTree(T2);
if(CmpTree(T1,T2)){
cout<<"相等"<<endl;
cout<<CountLeaf(T1,count);
}
//先序结果:A B D E C
// PreOrder(T);
//中序结果:D B E A C
//InOrder(T);
//后序结果:D E B C A
// PostOrder(T);
return 0;
}
太强了吧!