二叉树的先中后序遍历及相关常用算法

#include<string.h>#include<stdlib.h>typedefcharT;inti=0; //叶子结点数typedefstructbtnode 〃结点定义{TElement;structbtnode*LChild,*RChild;}BTNode;typedefstructbtree 〃头结点定义{structbtnode*Root;}BTree;BTNode*NewNode() 〃创建空间{BTNode*p=(BTNode*)malloc(sizeof(BTNode));returnp;}voidCreateBT(BTree*Bt) 〃创建一棵空二叉树{Bt->Root=NULL;}voidMakeBT(BTree*Bt,Tx,BTree*Lt,BTree*Rt)〃进行树的建立{BTNode*p=NewNode();p->Element=x;p->LChild=Lt->Root;p->RChild=Rt->Root;Lt->Root=Rt->Root=NULL;Bt->Root=p;}voidVisit(BTNode*p) 〃输出结点*P的元素值{printf("%c",p->Element);}voidPreOrd(void(*Visit)(BTNode*u),BTNode*t) 〃先序遍历递归函数if(t)(*Visit)(t);PreOrd(Visit,t->LChild);PreOrd(Visit,t->RChild);voidInOrd(void(*Visit)(BTNode*u),BTNode*t) 〃中序遍历递归函数{if(t){InOrd(Visit,t->LChild);(*Visit)(t);InOrd(Visit,t->RChild);}}voidPostOrd(void(*Visit)(BTNode*u),BTNode*t) //后序遍历递归函数{if(t){PostOrd(Visit,t->LChild);PostOrd(Visit,t->RChild);(*Visit)(t);}}voidPreOrder(BTreeBt,void(*Visit)(BTNode*u))〃先序遍历{PreOrd(Visit,Bt.Root);}voidInOrder(BTreeBt,void(*Visit)(BTNode*u)) 〃中序遍历{InOrd(Visit,Bt.Root);}voidPostOrder(BTreeBt,void(*Visit)(BTNode*u))〃后序遍历{PostOrd(Visit,Bt.Root);}intSize(BTNode*p) 〃树的结点数与叶子结点数的递归函数{ints,s1,s2;if(!p)return0;elses1=Size(p->LChild);s2=Size(p->RChild);s=s1+s2+1;if(s1==0&&s2==0)//判断是否是叶子节点{i++；printf("%3c",p->Element);returns;}else{returns;}}}intSizeofBT(BTreeBt) 〃树的结点数{returnSize(Bt.Root);}intDepth(BTNode*p) 〃树的高度递归函数{if(!p)return0;elsereturn1+max(Depth(p->LChild),Depth(p->RChild));}intDepthofBT(BTreeBt) //树的高度{returnDepth(BLRoot);}voidBreakBT(BTree*Bt,T*x,BTree*Lt,BTree*Rt) 〃树的拆分{BTNode*p=Bt->Root;if(p){x=p->Element;printf("根数：%c\n",x);Lt->Root=p->LChild;Rt->Root=p->RChild;Bt->Root=NULL;free(p);voidmain(void)BTreea,x,y,z;Te; 〃树的结点的元素intj,k; //树的结点数与高度CreateBT(&a);CreateBT(&x);CreateBT(&y);CreateBT(&z); 〃建立空树MakeBT(&x,'B',&a,&a);MakeBT(&x,'A',&x,&z);printf("遍历算法测试：\n");printf(" -\n");printf("先序遍历测试结果：”)；PreOrder(x,Visit);printf("\n中序遍历测试结果：”)；InOrder(x,Visit);printf("\n后序遍历测试结果：”)；PostOrder(x,Visit);printf("\n树的叶子结点为:");//建立树j=SizeofBT(x);k=DepthofBT(x);printf("\n树的叶子结点数为：%d\n",i);printf("树的结点数为：％d\n"j);printf("树的高度为：%d\n\n\n",k);printf("拆树算法测试：\n");printf(" -\n");BreakBT(&x,&e,&z,&y);printf(" -\n");printf("左孩子：\n");printf("先序遍历测试结果:")；PreOrder(z,Visit);printf("\n中序遍历测试结果:")；InOrder(z,Visit);printf("\n后序遍历测试结果:”)；PostOrder(z,Visit);i=0;printf("\n树的叶子结点为:");//建立树j=SizeofBT(z);k=DepthofBT(z);printf("\n树的叶子结点数为：%d\n",i);printf("树的结点数为：％d\n"j);printf("树的高度为：%d\n\n\n",k);printf(" -\n");printf("右孩子：\n");printf("先序遍历测试结果:")；PreOrder(y,Visit);printf("\n中序遍历测试结果:")；InOrder(y,Visit);printf("\n后序遍历测试结果:”)；PostOrder(y,Visit);i=0;printf("