南京工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)作業(yè)答案作業(yè)4

1、BA第四次作業(yè)1.設(shè)如下圖所示的二叉樹 B的存儲結(jié)構(gòu)為二叉鏈表，root為根指針,結(jié)點(diǎn)結(jié)構(gòu)為：(lchild,data,rchild ) o其中Ichild, rchild分別為指向左右孩子的指針，data為字符型,root為根指針，試回答下列問題：(1).對下列二叉樹B,執(zhí)行下列算法traversal(root),試指出其輸出結(jié)果；C的結(jié)點(diǎn)類型定義如下:struct node char data;struct node *lchild, rchild;：C 算法如下:void traversal(struct node *root)if (root)printf( “ c” ->dat

2、a);traversal(root->lchild); printf( “ %c” ->data);traversal(root->rchild);traversal(root)的時間復(fù)雜度。(2).假定二叉樹B共有n個結(jié)點(diǎn)，試分析算法6二叉樹B2試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點(diǎn)序列o3把如圖所示的樹轉(zhuǎn)化成二叉4畫出和下列二叉樹相應(yīng)的森林。(或:按層次輸出二叉樹中所有結(jié)5編寫按層次順序(同一層自左至右)遍歷二叉樹的算法 點(diǎn))。1.設(shè)如下圖所示的二叉樹B的存儲結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：(lchild,data,rchild )。其

3、中Ichild, rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：(1).對下列二叉樹B,執(zhí)行下列算法traversal(root),試指出其輸出結(jié)果；C的結(jié)點(diǎn)類型定義如下：struct nodechar data;struct node * Ichild, rchild;；C算法如下：void traversal(struct node *root)if (root)printf( “ %c" ->data);traversal(root->lchild); printf( “ %c”> data);traversal(r

4、oot->rchild);traversal(root)的時間復(fù)雜度。二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為：BADFFDGG特點(diǎn)：每個結(jié)點(diǎn)肯定都會被打印兩次；但出現(xiàn)的順序不同，其規(guī)律是：凡是有左子樹的結(jié)點(diǎn)，必間隔左子樹的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；如 A, B, D等結(jié)點(diǎn)。反之馬上就會重復(fù)出 現(xiàn)。女口 C, E, F, G等結(jié)點(diǎn)。時間復(fù)雜度以訪問結(jié)點(diǎn)的次數(shù)為主，精確值為 2F,時間漸近度為°(n)2.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點(diǎn)序列。答：DLR : ABDFJGKCEHILMLDR:BFJDGKACHELIMLR

5、D : JFKGDBHLMIECA答：注意全部兄弟之間都要連線（包 括度為2的兄弟），并注意原有連線結(jié)點(diǎn)一 律歸入左子樹，新添連線結(jié)點(diǎn)一律歸入右子 樹。4.畫出和下列二叉樹相應(yīng)的森林。答：注意根右邊的子樹肯定是森林，而 孩子結(jié)點(diǎn)的右子樹均為兄弟。遍歷二叉樹的算法點(diǎn)）O編寫按層次順序（同一層自左至右）（或:按層次輸出二叉樹中所有結(jié)解：思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結(jié)點(diǎn)的指針是個好辦法。這是一個循環(huán)算法，用while語句不斷循環(huán)，直到隊空之后自然退出該函數(shù)。技巧之處：當(dāng)根結(jié)點(diǎn)入隊后，會自然使得左、右孩子結(jié)點(diǎn)入隊，而左孩子出隊時又會立即使得它的 左右孩子結(jié)點(diǎn)入隊，以此產(chǎn)生了按層次輸出的效果。層序遍歷二叉樹的遞歸算法void LayerOrder(Bitree T)層序遍歷二叉樹(InitQueue(Q);/建立工作隊列En Queue(Q3T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p->