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