求树和二叉树的深度题目与源程序代码

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)/判栈空if(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