数据结构-二叉树各种算法实现

二叉树各种算法实现#includestdio.h#includemalloc.h#defineMAXSIZE20//二叉树结点的结构体表示形式typedefstructnode{chardata;structnode*left,*right;}BTree;//栈的结构体表示形式typedefstructstackelem{BTree*a[MAXSIZE];inttop;}Stack;//队列的结构体的表示形式typedefstructqueueelem{BTree*b[MAXSIZE];intfront,rear;}Queue;//创建二叉树，利用递归的方法BTree*Create(){charch;scanf(%c,&ch);getchar();if(ch=='#'){returnNULL;}else{BTree*btree=(BTree*)malloc(sizeof(BTree));if(btree==NULL){returnNULL;}btree-data=ch;btree-left=Create();btree-right=Create();returnbtree;}}//求二叉树的高度，递归实现intHeight(BTree*bt){intdepth1,depth2;if(NULL==bt){return0;}else{depth1=Height(bt-left);depth2=Height(bt-right);if(depth1depth2){return(depth1+1);}else{return(depth2+1);}}}intWidth(BTree*T)//二叉树宽度{intstaticn[10];//向量存放各层结点数intstatici=1;intstaticmax=0;//最大宽度if(T){if(i==1)//若是访问根结点{n[i]++;//第1层加1i++;//到第2层if(T-left)//若有左孩子则该层加1n[i]++;if(T-right)//若有右孩子则该层加1n[i]++;}else{//访问子树结点i++;//下一层结点数if(T-left)n[i]++;if(T-right)n[i]++;}if(maxn[i])max=n[i];//取出最大值Width(T-left);//遍历左子树i--;//往上退一层Width(T-right);//遍历右子树}returnmax;}//层次遍历二叉树,用队列来实现voidTraversalOfLevel(BTree*bt){Queueq;q.front=q.rear=0;if(bt!=NULL){printf(%c,bt-data);}q.b[q.front]=bt;q.rear=q.rear+1;while(q.frontq.rear){bt=q.b[q.front];q.front=q.front+1;if(bt-left!=NULL){printf(%c,bt-left-data);q.b[q.rear]=bt-left;q.rear=q.rear+1;}if(bt-right!=NULL){printf(%c,bt-right-data);q.b[q.rear]=bt-right;q.rear=q.rear+1;}}}intleafcount(BTree*root)//统计叶子结点个数{if(root==NULL)return0;else{if(!root-right&&!root-left)return1;elsereturnleafcount(root-left)+leafcount(root-right);}}intCountNode(BTree*t)//节点总数{intnum;if(t==NULL)num=0;elsenum=1+CountNode(t-left)+CountNode(t-right);return(num);}BTree*copy(BTree*p)//复制一棵二叉树{BTree*temp;if(p==NULL)returnNULL;temp=(BTree*)malloc(sizeof(BTree));temp-data=p-data;temp-left=copy(p-left);temp-right=copy(p-right);returntemp;}/*判断两棵二叉树是否相似的递归算法*/intSimilar(BTree*t1,BTree*t2){if(t1==NULL&&t2==NULL)return1;if(t1&&t2){if(Similar(t1-left,t2-left)&&Similar(t1-right,t2-right)){return1;}}return0;}intCompTree(BTree*tree1,BTree*tree2)//二叉树是否相等{if(!tree1&&!tree2){return1;}elseif(tree1-data==tree2-data&&CompTree(tree1-left,tree2-left)&&CompTree(tree1-right,tree2-right)){return1;}else{return0;}}intmain(){BTree*btr=Create();printf(叶子结点个数为：\n);intleafgs=leafcount(btr);printf(%d\n,leafgs);printf(结点总数为：\n);intcountn=CountNode(btr);printf(%d\n,countn);printf(度为1的结点个数为：%d\n,countn-2*leafgs+1);printf(度为2的结点个数为：%d\n,leafgs-1);printf(二叉树的高度：\n);intHgt=Height(btr);printf(%d\n,Hgt);printf(二叉树的宽度：\n);intWdh=Width(btr);printf(%d\n,Wdh);printf(层次遍历二叉树:\n);TraversalOfLevel(btr);printf(\n);printf(复制的二叉树为:\n);BTree*cp=copy(btr);TraversalOfLevel(cp);printf(\n);if(Similar(btr,cp)==1)printf(此两二叉树相似\n);elseprintf(此两二叉树不相似\n);if(CompTree(btr,cp)==1)printf(此两二叉树相等\n);elseprintf(此两二叉树不相等\n);return0;}运行截图：