第6章 樹和二叉樹

《第6章 樹和二叉樹》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、6.1若二叉樹中各結點的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。(1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫出此二叉樹。ABCDEFGHI(2)已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請畫出此二叉樹。(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請畫出這兩棵不同的二叉樹。AABB實例2：試編寫算法交換二叉樹中所有結點的左、右

2、子樹（自選存儲結構）。voidexchg_tree(bitreptrBT)/*本算法采用后根遍歷遞歸訪問的方法，交換每一個結點的左右子樹。*/{if(BT!=null)/*非空*/{exchg_tree(BT->lchild);/*交換左子樹所有結點指針*/exchg_tree(BT->rchild);/*交換右子樹所有結點指針*/p=BT->lchild;/*交換根結點左右指針*/BT->lchild=BT->rchild;BT->rchild=p;}}實例3：有一二叉鏈表，按后根遍歷時輸出的結點順序為a1,a2,…aa

3、n。試編寫一算法，要求輸出后根序列的逆序an,an-1…，a2,a1。voidpreorder(treeT){if(T!=NULL){printf(“%f”,T->data);preorder(T->rchild);preorder(T->lchild);}}實例4:有一二叉鏈表，試編寫按層次順序遍歷二叉樹的算法。本算法要借用隊列來完成，其基本思想是，若二叉樹非空，先將根結點進隊列。然后進入循環(huán)：只要隊列不空，就出隊列，遍歷該結點，然后判斷出隊列的結點是否有左孩子和右孩子，如有就讓左、右孩子進隊列。voidlayorder

4、(treeT){initqueue(q)/*隊列初始化*/if(T!=NULL){enqueue(q,T);/*入隊列*/while(notemptyqueue(q))/*若隊列非空*/{outqueue(q,p);/*出隊*/printf(“%f”,p->data);if(p->lchild!=NULL)enqueue(q,p->lchild);/*入隊列*/if(p->rchild!=NULL)enqueue(q,p->rchild);/*入隊列*/}/*endofwhile(notemptyqueue(q))*/}}

5、實例5：設n個元素的先序序列已存在數組A中，試建立起二叉樹的二叉鏈表存儲結構。treecreate(r,A)treer;charA[n];{charc;statici=0;c=A[i];i++;if(c==’’)r=null;else{r=(tree*)malloc(sizeof(treenode))if(!r)exit(0);r->data=c;r->lchild=create(r->lchild,A);/*遞歸建立左子樹*/r->rchild=create(r->rchild,A);/*遞歸建立右子樹*/}return

6、(r);}實例6：求二叉樹的葉子數。intcountleaf(r);treer;{statici=0;if(r){if((r->lchild==null)&&(r->rchild==null))i++;/*葉子結點*/countleaf(r->lchild);/*遞歸求左子樹中葉子數*/countleaf(r->rchild);/*遞歸求右子樹中葉子數*/}return(i);}實例7：統(tǒng)計二叉樹中結點的個數voidCountnode(BiTreeT,int&node){//在實際使用時，node作為全局變量，其初始值為0

7、if(T){node++;Countnode(T->lchild,node);Countnode(T->rchild,node);}//if}//Countnode實例8：求二叉樹的深度的算法(后序遍歷)intDepth(BiTreeT){//返回二叉樹的深度if(T){depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}elsedepthval=0;re

8、turndepthval;}