數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章-預(yù)覽頁
【正文】 (g+h)轉(zhuǎn)化為二叉樹。若該結(jié)點(diǎn)不存在，則取0值。6．假設(shè)前序遍歷某棵樹的結(jié)點(diǎn)次序?yàn)镾ACEFBDGHIJK；后序遍歷該樹的結(jié)點(diǎn)次序?yàn)镃FEABHGIKJDS，請(qǐng)畫出這棵樹。，鏈結(jié)點(diǎn)的構(gòu)造為：其中若ltag為0，則lchild指向結(jié)點(diǎn)的前驅(qū)，否則lchild指向左孩子結(jié)點(diǎn)；若rtag為0，則rchild指向結(jié)點(diǎn)的后繼，否則rchild指向右孩子結(jié)點(diǎn)。 x) while s=srchild。 return s；棧已經(jīng)定義：InitStack(S)（初始化）、Empty(S)（判?？眨?、Push(S，p)（入棧）、Pop(S，p)（出棧）等操作。4．設(shè)中序線索樹的結(jié)點(diǎn)由5個(gè)域組成。 LT:標(biāo)志域，為0或1。 當(dāng)LT為0時(shí)，給出按中序遍歷的前驅(qū)結(jié)點(diǎn)地址。 RL：當(dāng) RT為1時(shí)，給出該結(jié)點(diǎn)的右孩子的地址。 請(qǐng)編寫 程序，在具有上述結(jié)點(diǎn)結(jié)構(gòu)的中序線索二叉樹上，求某一結(jié)點(diǎn)p按后序遍歷次序的后繼結(jié)點(diǎn)的地址q，設(shè)該中序線索二叉樹的根結(jié)點(diǎn)地址為r。7．以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫出交換各結(jié)點(diǎn)左右子樹的算法。 1．B2．B3．C 9．A，B (2)A (6)A 11．B 16．D 20．D 6．前序遍歷，中序遍歷。 7．前序，中序，后序，前序，后序。 8. 2i1， 「2/n, 235。 11. 2n，nl，n+l。 12．A 18. 2nl。 19. 560 √ 5. 8. 中序：c，b，a，e，d，D 由中序和后序（前序）遍歷序列可惟一確定一棵二叉樹，基本思想是后序（前序）定根，中序分左右。對(duì)以f為根結(jié)點(diǎn)的子樹可做類似的分析。 a(b(c，d(，e))，f(g(，h(i，j))))，由此可知該樹： 葉結(jié)點(diǎn)：4。 3．已知一棵樹邊的集合為{I，M，I，N，E，I，B，E，B，D，A，B，GJ，G K，C，G，C，F(xiàn)，H，L，C，H，A，C}，請(qǐng)畫出這棵樹，并回答問題？數(shù)組BT的存放形式是相對(duì)于滿二叉樹中編號(hào)為數(shù)組下標(biāo)值的結(jié)點(diǎn)值。 8．空樹滿足所有條件。 (1)前序和中序遍歷序列相同的二叉樹是沒有左子樹的二叉樹（右單支樹）。 (2)中序和后序遍歷序列相同的二叉樹是沒有右子樹的二叉樹（左單支樹）。 (3)前序和后序遍歷序列相同的二叉樹是只有根的二叉樹。 9．在信息“ABCD BCD CB DB ACB”中A，B，C，D四個(gè)字符出現(xiàn)的頻率依次是：2，5，4，3。 在哈夫曼樹中每個(gè)字符的最優(yōu)編碼： 信息編碼為：110010111 010111 void InorderTraverse (BTree T)amp。 )p=prchild)。 } }試以此存儲(chǔ)結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞推形式的算法。 【解答】要解決這一問題必須區(qū)分結(jié)點(diǎn)在訪問過程中的狀態(tài)，這可通過結(jié)點(diǎn)的標(biāo)志域來處理。 (3)其右予樹遍歷結(jié)束轉(zhuǎn)換。void postorder (BTree T)switch (pflag) if (plchild) p=plchild。 case l:p=pparent 。 preorder (int R[]，int n，int t) 若x是parent的右孩子，則parent是x的最左子孫的左線索。 因此設(shè)計(jì)兩個(gè)函數(shù)求給定結(jié)點(diǎn)的最左子孫的左線索和最右子孫的右線索。 Pointer typedefStruct *BiThrNode。 enum{ lEFT, RIGHT)BiTHrNode *LeftMose( BiTHrTree //求T的最左子孫的左線索if (plchild) return NULL。} *RightMost (BiTHrTree T) if (prchild) Isrightchild (BiThrTree T,BiThrTree {if (parent＆＆parentrchild==p)else O。 } posttraverse—InThrTree (BiTheTree T)Tagtype tag。 //待訪問標(biāo)志，表示當(dāng)前結(jié)點(diǎn)是從左孩子還是右孩子返回的 else tag=RIGHT。 tag=RIGHT。 if} } ispace。 pdata)。 disp (Tlchild, enumf Link，Thread)PointerTag。 //Link:0指針，Thread:1線索 Ltag, Rtag。 } ) //右鏈域?yàn)橹羔?，則轉(zhuǎn)右于樹，繼續(xù)右于樹前序遍歷 算法時(shí)間復(fù)雜度為O(n)。 7．以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫出交換各結(jié)點(diǎn)左右子樹的算法。 【解答】要交換各結(jié)點(diǎn)的左右子樹，最方便的辦法是用后序遍歷算法，每訪問一個(gè)結(jié)點(diǎn)時(shí)把兩棵子樹的指針進(jìn)行交換，最后一次訪問是交換根結(jié)點(diǎn)的子樹。 typedef char DataType。 //定義DaTaType類型 void ChangeBinTee (BinTree //交換子樹 ChangeBinTree(＆(*T) rchlld)。 void PrintNode (BinTree T)PrintNode (Tlchild)。 void main()ChangeBinTree( amp。 }
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1