數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章-資料下載頁(yè)
2025-06-22 21:25本頁(yè)面
【正文】 else //p是左孩子，用最右的線索找雙親結(jié)點(diǎn) { p=RightMost (p)。 if (p＆＆pRtag==Thread) tag=RIGHT。 else tag=LEFT。 } } if (tag==LEFTamp。＆p) p=prchild。 } } 5．凹入表示法打印二叉樹(shù)： 采用前序遍歷的遞歸函數(shù)依次輸出各結(jié)點(diǎn)的值，子結(jié)點(diǎn)比父結(jié)點(diǎn)右縮進(jìn)3個(gè)字符寬度，具體實(shí)現(xiàn)算法如下： Void disp (BiTree T， int space) //space為空格數(shù) { int i。 if (t) { for (i=l。 ispace。 i++) printf( )。 //輸出space個(gè)空格 printf(”%d\n168。, pdata)。 disp (Tlchild, space+3)。 disp (Trchild, space+3)。 } } 6．前序遍歷一棵中序線索樹(shù)： 在不使用棧和遞歸的情況下對(duì)線索二叉樹(shù)進(jìn)行前序遍歷，需要知道任意結(jié)點(diǎn)前序的直接后繼。 typedef enumf Link，Thread)PointerTag。 //Link:0指針，Thread:1線索 typedef struct BiThrNodet //中序線索樹(shù)結(jié)點(diǎn)結(jié)構(gòu) ElemType data。 Struct BiThrNode lchild, rchild。 PointerTag Ltag, Rtag。 } BiThrNode, *BiThrTree 。 void pretraverse—thread(BiThrTree T) //前序遍歷帶頭結(jié)點(diǎn)的中序線索樹(shù)T { BiTrhTree p=Tlchild。 while(p!=T) { while (pLtag==Link) //遍歷到最左端 { visit (p)。 p=plchild。) visit (p)。 //訪問(wèn)最左端結(jié)點(diǎn)，然后向右轉(zhuǎn) while (pRtag==Thread) //由右線索向上 p=p rchild。 if (pRtag==link) //右鏈域?yàn)橹羔?，則轉(zhuǎn)右于樹(shù)，繼續(xù)右于樹(shù)前序遍歷 p=prchild。 } } 算法時(shí)間復(fù)雜度為O(n)。 7．以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫(xiě)出交換各結(jié)點(diǎn)左右子樹(shù)的算法。 【解答】要交換各結(jié)點(diǎn)的左右子樹(shù)，最方便的辦法是用后序遍歷算法，每訪問(wèn)一個(gè)結(jié)點(diǎn)時(shí)把兩棵子樹(shù)的指針進(jìn)行交換，最后一次訪問(wèn)是交換根結(jié)點(diǎn)的子樹(shù)。算法如下： typedef char DataType。 //定義DaTaType類(lèi)型 typedef struct node { DataType data。 struct node lchild，rchild。 //左右孩子子樹(shù) } BinNode。 //結(jié)點(diǎn)類(lèi)型 typedef BinNode *BinTree。 includestdio．H void ChangeBinTee (BinTree *T) //交換子樹(shù) { if(*T) //這里以指針為參數(shù)使交換在實(shí)參的結(jié)點(diǎn)上進(jìn)行 { BinTreetemp。 //后序遍歷 ChangeBinTree(＆(*T) lchild)。 ChangeBinTree(＆(*T) rchlld)。 temp= (*T) lchild。 (*T) lchild= (*T) rchild。 (*T) rchild=temp。 } } void PrintNode (BinTree T) //以前序序列打印結(jié)點(diǎn)數(shù)據(jù) { if (T) { Printf(168。%C, Tdata)。 PrintNode (Tlchild)。 PrintNode( Trchiid)。 } } void main() //測(cè)試程序 { BinTree root。 CreatBinTree( amp。root)。 //建立二叉鏈表 PrintNode (root)。 //輸出原表 printf( \n)。 ChangeBinTree( amp。root)。 //交換子樹(shù) PrintNode (root)。 //輸出新表 printf(＼n)。 }
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1