【正文】 第 6章 樹和二叉樹 后序線索二叉樹 void PostThreading(TriThrTree p) { if( p ) { PostThreading( plchild )。 PostThreading( prchild )。 if( !plchild ) { pLTag = Thread。 plchild = pre。 } if ( !prchild ) pRTag = Thread。 if ( pre amp。amp。 preRTag == Thread) prerchild = p。 pre = p。 } }//PostThreading 優(yōu)點： 對于遍歷操作，線索樹優(yōu)于非線索樹，遍歷線索樹不用設棧 數(shù)據(jù)結構 第 6章 樹和二叉樹 void InThreading( BiThrTree p ){ //中序線索化 if(p) { InThreading(plchild)。 //左子樹線索化 if(!plchild) { pLTag = Thread。 plchild = pre。 } //前驅線索 if(!prerchild) { preRTag = Thread。 prerchild = p。 } //后繼線索 pre = p。 //保持 pre指向 p的前驅 InThreading(prchild)。 //右子樹線索 } }//InThreading 數(shù)據(jù)結構 第 6章 樹和二叉樹 六、樹和森林 樹的存儲結構 森林與二叉樹的轉換 樹和森林的遍歷 數(shù)據(jù)結構 第 6章 樹和二叉樹 樹的存儲結構 （ 1）雙親表示法： 以一組連續(xù)空間存儲樹的結點，同時在每個結點中附設一個指示器指示其雙親結點在鏈表中的位臵，其形式說明如下： define MAX_TREE_SIZE 100 typedef struct PTNode{ //結點結構 TElemType data。 int parent。 //雙親位臵域 }PTNode。 typedef struct{ //樹結構 PTNode nodes[MAX_TREE_SIZE]。 int r, n。 //根的位臵和結點數(shù) }PTree 數(shù)據(jù)結構 第 6章 樹和二叉樹 樹的雙親表示法示例 ACBDRE FG KHR A B C D E F G H K 1 0 1 2 3 4 5 6 7 8 9 0 0 0 1 1 3 6 6 6 數(shù)組下標 優(yōu)點 ： PARENT(T, x)操作可以在常量時間內實現(xiàn) 缺點 ： 求結點的孩子時需要遍歷整個結構 數(shù)據(jù)結構 第 6章 樹和二叉樹 （ 2）孩子表示法： 由于樹中每個結點有多棵子樹，可使用多重鏈表表示樹，其每個結點有多個指針域，其中每個指針指向一棵子樹的根結點。其結點有如下兩種格式。如下圖： child1 data child2 childd … degree data child1 child2 childd … 第一種格式： 結點同構 ，鏈表中會產生許多空鏈域，浪費空間； 容易證明： 在一棵有點 n個結點度為 k的樹中必有 n(k1)+1個空鏈域。 第二種格式： 結點不同構 ，空間比較節(jié)約，但操作不方便。 數(shù)據(jù)結構 第 6章 樹和二叉樹 另外一種辦法：每個結點的孩子排列起來，看成一個線性表，以單鏈表作為存儲結構。則 n個結點有 n個孩子鏈表（葉子的孩子鏈表為空表）。 n個頭指針又組成一個線性表，為便于查找，可采用順序存儲結構。 typedef struct CTNode{ //孩子結點 int child。 struct CTNode *next。 }*ChildPtr。 typedef struct{ TElemType data。 ChildPtr firstchild。 //孩子鏈表頭指針 }CTBox。 typedef struct{ CTBox nodes[MAX_TREE_SIZE]。 int n, r。 //結點數(shù)和根的位臵 。 }CTree。 數(shù)據(jù)結構 第 6章 樹和二叉樹 樹的孩子鏈表表示法示例 A CBDRE FG KH優(yōu)點 ： CHILD(T, i, amp。x)操作可以在常量時間內實現(xiàn) 缺點 ： PARENT(T, x)需要遍歷整個結構 解決方法 ： 將雙親表示法和孩子表示法結合起來進行操作 0123456789ABCDREFGHK^^^^^^3^50 16 ^2^9 ^8740123567891444002666數(shù)據(jù)結構 第 6章 樹和二叉樹 （ 3）孩子兄弟表示法： 又稱 二叉樹表示法 ，或 二叉鏈表表示法 。即以二叉鏈表做樹的存儲結構，鏈表中的兩個鏈域分別指向該結點的 第一個孩子結點 和 下一個兄弟結點 。其形式說明如下： typedef struct CSNode{ ElemType data。 struct CSNode *firstchild, *nextsibling。 }CSNode, *CSTree。 數(shù)據(jù)結構 第 6章 樹和二叉樹 樹的孩子兄弟表示法示例 A CBDRE FG KHR^AD^B^E^ ^C^F^G^H^K^ ^優(yōu)點 ：便于實現(xiàn)各種樹的操作 數(shù)據(jù)結構 第 6章 樹和二叉樹 森林與二叉樹的轉換 ? 由于二叉樹和樹都可用二叉鏈表作為存儲結構，則以二叉鏈表作為媒介可導出樹與二叉樹之間的一個 對應關系 。 ?給定一棵樹，可以找到 唯一 的一棵二叉樹 與之對應 。從物理結構來看，他們的二叉鏈表表示相同，只是解釋不同。 如圖所示 ?樹的根結點無兄弟結點，其對應的二叉樹的 右子樹必為空 。若把森林中的第二棵樹的根結點看成是第一棵樹的根結點的兄弟，則同樣可以導出森林與二叉樹之間的對應關系。 數(shù)據(jù)結構 第 6章 樹和二叉樹 樹轉換成二叉樹的方法 (1) 在同胞兄弟之間加連線； A B C E D A B C E D (2) 保留結點與第一個孩子之間的連線，去掉其余連線； A B C E D (3) 將結點與孩子之間的連線調整為垂直線，將同胞兄弟之間的連線調整為水平線； A B C E D (4) 以根結點為軸， 順時針 旋轉 45度。 數(shù)據(jù)結構 第 6章 樹和二叉樹 二叉樹轉換成樹的方法 ABFCED(1) 將每個結點的左孩子沿及其右鏈訪問到的所有結點與左孩子的雙親之間加連線； ABFCED(2) 將結點與右鏈之間的連線去掉； ABFCED(3) 將所有的兄弟結點調整在同一水平線上，并作適當?shù)慕嵌日{整。 ABFCED數(shù)據(jù)結構 第 6章 樹和二叉樹 森林轉換成二叉樹的方法 (1) 將每棵樹轉化成二叉樹； (2) 將第一棵樹的樹根作為整棵二叉樹的樹根； (3) 將剩余的每棵樹依次連接到二叉樹的右子樹上。 ACB DEFGH IJABCDEFGHIJ樹 與 二 叉 樹 對 應AB ECDF GHIJ樹根相連森 林 與 二 叉 樹 對 應數(shù)據(jù)結構 第 6章 樹和二叉樹 樹與森林的遍歷 樹的遍歷有兩種： 先根遍歷 ：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹；（等價于二叉樹的先序遍歷） 后根遍歷 ：先依次后根遍歷每棵子樹，然后訪問根結點。 （等價于樹的中序遍歷） BECAD先根序列 ： ABCDE 后根序列 ： BDCEA 數(shù)據(jù)結構 第 6章 樹和二叉