1、樹和二叉樹以下問題要求統一在一個大程序里解決。10、按先序遍歷的擴展序列建立二叉樹的存儲構造11、二叉樹先序、中序、后序遍歷的遞歸算法12、二叉樹中序遍歷的非遞歸算法13、二叉樹層次遍歷的非遞歸算法14、求二叉樹的深度(后序遍歷)15、建立樹的存儲構造16、求樹的深度17、源程序代碼：/tree.cpp:Definestheentrypointfortheconsoleapplication./#includestdafx.h#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defin

2、eOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefcharTElemType;/元素數據類型typedefintStatus;/*二叉鏈表儲存構造*/typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;boolCreateBiTree(BiTree&T)/先序序列建立二叉樹charch;scanf(%c,&ch);if(ch=*)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeo

3、f(BiTNode)returnERROR;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);returnOK;StatusPrintElement(TElemTypee)/訪問函數printf(%c,e);returnOK;StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/先序遍歷二叉樹的遞歸算法if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Vi

4、sit)returnOK;returnERROR;elsereturnOK;StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/中序遍歷二叉樹的遞歸算法if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)returnOK;returnERROR;elsereturnOK;StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/后序遍歷二叉樹的遞歸算法i

5、f(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)returnOK;returnERROR;elsereturnOK;/*棧存儲構造及操作*/typedefstructBiTree*base;BiTree*top;intstacksize;Stack;StatusInitStack(Stack&S)/構造空棧S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)exit(OVERFLOW

6、);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;StatusGetTop(StackS,BiTree&e)/讀棧頂元素if(S.top=S.base)returnERROR;e=*(S.top-1);returnOK;StatusPush(Stack&S,BiTreee)/入棧if(S.top-S.base=S.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)exit(OVERFLOW);S.to

7、p=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;StatusPop(Stack&S,BiTree&e)/出棧if(S.top=S.base)returnERROR;e=*-S.top;returnOK;StatusStackEmpty(StackS)/判?？読f(S.base=S.top)returnTRUE;elsereturnFALSE;StatusInOrderTraverse2(BiTreeT,Status(*Visit)(TElemType)/中序遍歷二叉樹的非遞歸算法StackS;BiTreep

8、;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);if(!Visit(p-data)returnERROR;Push(S,p-rchild);returnOK;#defineMAXLEN100voidLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/層次遍歷二叉樹structnodeBiTreevecMAXLEN;intf,r;q;q.f=0;q.r=0;if

9、(T!=NULL)Visit(T-data);q.vecq.r=T;q.r=q.r+1;while(q.flchild!=NULL)Visit(T-lchild-data);q.vecq.r=T-lchild;q.r=q.r+1;if(T-rchild!=NULL)Visit(T-rchild-data);q.vecq.r=T-rchild;q.r=q.r+1;intBiTreeDepth(BiTreeT)/求二叉樹的深度intdepthval,depthLeft,depthRight;if(!T)depthval=0;elsedepthLeft=BiTreeDepth(T-lchild);d

10、epthRight=BiTreeDepth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;/*樹的二叉鏈表儲存構造*/typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;/*隊列存儲構造及操作*/typedefstructQNodeCSTreedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfron

11、t;QueuePtrrear;LinkQueue;StatusInitQueue(LinkQueue&Q)/構造空隊列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;StatusDestoryQueue(LinkQueue&Q)/銷毀隊列while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;returnOK;StatusEnQueue(LinkQueue&Q,CSTreee

12、)/入隊QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;StatusDeQueue(LinkQueue&Q,CSTree&e)/出隊QueuePtrp;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;StatusGetHead

13、(LinkQueue&Q,CSTree&e)/讀隊頭QueuePtrp;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;returnOK;CSTreeGetTreeNode(TElemTypee)/建立樹的孩子/-兄弟鏈表結點CSTreep;p=(CSTree)malloc(sizeof(CSNode);if(!p)exit(OVERFLOW);p-data=e;p-firstchild=NULL;p-nextsibling=NULL;returnp;StatusCreatTree(CSTree&T)/建立樹的孩子/-兄弟鏈表char

14、first=,second=;intresult=0;LinkQueueQ;CSTreep,s,r;InitQueue(Q);T=NULL;for(scanf(%c%c,&first,&second);second!=#;result=scanf(%c%c,&first,&second)p=GetTreeNode(second);EnQueue(Q,p);if(first=#)T=p;elseGetHead(Q,s);while(s-data!=first)DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;elser-

15、nextsibling=p;r=p;returnOK;intTreeDepth(CSTreeT)/求樹的深度inth1,h2;if(!T)return0;elseh1=TreeDepth(T-firstchild);h2=TreeDepth(T-nextsibling);return(h1+1)h2)?(h1+1):h2);intmain(intargc,char*argv)BiTreetestT;printf(請輸入二叉樹先序序列如AB*C*：);CreateBiTree(testT);printf(n);printf(二叉樹的深度是：);printf(%d,BiTreeDepth(testT);printf(n);printf(先序遞歸遍歷順序：);PreOrderTraverse(testT,PrintElement);printf(n);printf(中序遞歸遍歷順序：);InOrderTraverse(testT,PrintElement);printf(n);printf(后序遞歸遍歷順序：);PostOrderTraverse(testT,PrintElement);printf(n);printf(層次非遞歸遍歷順序：);LevelOrderTraverse(testT,PrintElement