您當(dāng)前位置：首頁 > 數(shù)據(jù)庫 > 數(shù)據(jù)庫應(yīng)用 > 數(shù)據(jù)結(jié)構(gòu) - 樹和森林表示與遍歷

數(shù)據(jù)結(jié)構(gòu) - 樹和森林表示與遍歷

來源：程序員人生發(fā)布時間：2015-05-19 08:32:33 閱讀次數(shù)：3366次

雙親表示法(順序存儲結(jié)構(gòu))

      用1組連續(xù)的存儲空間來存儲樹的結(jié)點，同時在每一個結(jié)點中附加1個唆使器(整數(shù)域) ，用以唆使雙親結(jié)點的位置(下標(biāo)值) 。數(shù)組元素及數(shù)組的類型定義以下：

＃define MAX_SIZE  100
typedef  struct PTNode
{  ElemType  data ;
int  parent ;
}PTNode ;

typedef  struct
{  PTNode  Nodes[MAX_SIZE] ;
int  root;    /*  根結(jié)點位置  */
int  num ;   /*  結(jié)點數(shù)   */ 
}Ptree ;

所示是1棵樹及其雙親表示的存儲結(jié)構(gòu)。這類存儲結(jié)構(gòu)利用了任1結(jié)點的父結(jié)點唯1的性質(zhì)。可以方便地直接找到任1結(jié)點的父結(jié)點，但求結(jié)點的子結(jié)點時需要掃描全部數(shù)組。

孩子鏈表表示法

2 孩子鏈表表示法
樹中每一個結(jié)點有多個指針域，每一個指針指向其1棵子樹的根結(jié)點。有兩種結(jié)點結(jié)構(gòu)。
⑴ 定長結(jié)點結(jié)構(gòu)
指針域的數(shù)目就是樹的度。
其特點是：鏈表結(jié)構(gòu)簡單，但當(dāng)樹中各結(jié)點的度相差很大時，指針域的浪費明顯。但如果樹的各結(jié)點的度相差很小時，那開辟的空間被充分利用了，這類存儲結(jié)構(gòu)的缺點就變成了優(yōu)點。
結(jié)點結(jié)構(gòu)

⑵ 不定長結(jié)點結(jié)構(gòu)（按需分配）
樹中每一個結(jié)點的指針域數(shù)量不同，是該結(jié)點的度。沒有過剩的指針域，但操作不便。
優(yōu)點：空間利用率提高了
缺點：各個結(jié)點的鏈表結(jié)構(gòu)不相同，實現(xiàn)起來比較困難；
其次要保護結(jié)點的度的值，運算上會帶來時間的消耗。

⑶ 復(fù)合鏈表結(jié)構(gòu)
（順序存儲+鏈?zhǔn)酱鎯Γ?
具體辦法是：把所有結(jié)點放到1個順序存儲的數(shù)組中，然后將每一個結(jié)點的孩子結(jié)點排列起來，用單鏈表作存儲結(jié)構(gòu)（由于每一個結(jié)點的孩子數(shù)不肯定）。

    n個結(jié)點的樹有n個（孩子）單鏈表(葉子結(jié)點的孩子鏈表為空)；
   n個頭結(jié)點又組成1個線性表，采取順序存儲結(jié)構(gòu)，寄存進1個1維數(shù)組中。

設(shè)計兩種結(jié)點結(jié)構(gòu)：
表頭數(shù)組的表頭結(jié)點: (firstchild存儲該結(jié)點的孩子鏈表的頭指針）；
孩子鏈表的表結(jié)點：(childno用來存儲某個結(jié)點在表頭數(shù)組中的下標(biāo)，next指向下1個孩子）。

數(shù)據(jù)結(jié)構(gòu)類型定義

數(shù)據(jù)結(jié)構(gòu)類型定義以下：

＃define  MAX_NODE  100
typedef  struct  listnode
{   int   childno ;    /*  孩子結(jié)點編號  */
struct listno  *next ;
}CTNode;    /*  表結(jié)點結(jié)構(gòu)  */
typedef  struct
{  ElemType   data ;
CTNode  *firstchild ;
}HNode;    /*  頭結(jié)點結(jié)構(gòu)  */

typedef  struct
{  HNode   nodes[MAX_NODE] ;
int  root;    /*  根結(jié)點位置  */
int  num ;   /*  結(jié)點數(shù)   */
}CLinkList;    /*  頭結(jié)點結(jié)構(gòu)  */
復(fù)合鏈表結(jié)構(gòu)點評：
優(yōu)點：便于查找結(jié)點的孩子或結(jié)點的兄弟
缺點：查找某結(jié)點的雙親需遍歷整棵樹

孩子兄弟表示法(2叉樹表示法)

3 孩子兄弟表示法(2叉樹表示法)

  樹有以下特點：任意1棵樹，它的結(jié)點的第1個孩子如果存在就是唯1的，它的兄弟如果存在也是唯1的。因此，設(shè)置兩個指針，分別指向該結(jié)點的第1個孩子和它的右兄弟結(jié)點。結(jié)點類型定義以下：

typedef  struct   CSnode
{  ElemType   data ;
struct   CSnode *firstchild, *nextsib ;
}CSNode;

孩子兄弟表示法點評：
便于查找某個結(jié)點的孩子
通過firstchild找到該結(jié)點的長子，然后通太長子結(jié)點的nextsib找到次子……直到找到要找的孩子。
難以找到雙親
解決辦法：增加1個雙親parent指針域

森林與2叉樹的轉(zhuǎn)換

     由于2叉樹和樹都可用2叉鏈表作為存儲結(jié)構(gòu)，對照各自的結(jié)點結(jié)構(gòu)可以看出，以2叉鏈表作為媒介可以導(dǎo)出樹和2叉樹之間的1個對應(yīng)關(guān)系。

◆ 從物理結(jié)構(gòu)來看，樹和2叉樹的2叉鏈表是相同的，只是對指針的邏輯解釋不同而已。
◆ 從樹的2叉鏈表表示的定義可知，任何1棵和樹對應(yīng)的2叉樹，其右子樹1定為空。

樹轉(zhuǎn)換成2叉樹
對1般的樹，可以方便地轉(zhuǎn)換成1棵唯1的2叉樹與之對應(yīng)。其詳細(xì)步驟是：
⑴ 加虛線。在樹的每層按從“左至右”的順序在兄弟結(jié)點之間加虛線相連。
⑵ 去連線。除最左的第1個子結(jié)點外，父結(jié)點與所有其它子結(jié)點的連線都去掉。
⑶ 旋轉(zhuǎn)。將樹順時針旋轉(zhuǎn)450，原本的實線左斜。
⑷ 整型。將旋轉(zhuǎn)后樹中的所有虛線改成實線，并向右斜

3 森林轉(zhuǎn)換成2叉樹
當(dāng)1般的樹轉(zhuǎn)換成2叉樹后，2叉樹的右子樹必為空。若把森林中的第2棵樹(轉(zhuǎn)換成2叉樹后)的根結(jié)點作為第1棵樹(2叉樹)的根結(jié)點的兄弟結(jié)點，則可導(dǎo)出森林轉(zhuǎn)換成2叉樹的轉(zhuǎn)換步驟以下：
1、把每棵樹轉(zhuǎn)換為2叉樹
2、按給出的森林中樹的次序，第1棵樹不動，從第2棵樹開始，順次把后1棵樹的根結(jié)點作為前1棵2叉樹的根結(jié)點的右孩子，用線連起來，當(dāng)所有的2叉樹連接起來后，就得到了由森林轉(zhuǎn)換來的2叉樹。

樹和森林的遍歷

這里寫圖片描述
1 樹的遍歷
由樹結(jié)構(gòu)的定義可知，樹的遍歷有2種方法。
⑴ 先序遍歷：先訪問根結(jié)點，然后順次先序遍歷完每棵子樹。如圖的樹，先序遍歷的次序是：
ABCDEFGIJHK
⑵ 后序遍歷：先順次后序遍歷完每棵子樹，然后訪問根結(jié)點。如圖的樹，后序遍歷的次序是：
CDBFGIJHEKA
說明：
◆ 樹的先序遍歷實質(zhì)上與將樹轉(zhuǎn)換成2叉樹后對2叉樹的先序遍歷相同。
◆ 樹的后序遍歷實質(zhì)上與將樹轉(zhuǎn)換成2叉樹后對2叉樹的中序遍歷相同。
2 森林的遍歷
設(shè)F={T1, T2,?,Tn}是森林，對F的遍歷有2種方法。
⑴ 先序遍歷：按先序遍歷樹的方式順次遍歷F中的每棵樹。
⑵ 中序遍歷：按中序遍歷樹的方式順次遍歷F中的每棵樹。