您當前位置：首頁 > 數據庫 > 數據庫應用 > 數據結構 - 樹和森林表示與遍歷

數據結構 - 樹和森林表示與遍歷

來源：程序員人生發布時間：2015-05-19 08:32:33 閱讀次數：3376次

雙親表示法(順序存儲結構)

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

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

typedef  struct
{  PTNode  Nodes[MAX_SIZE] ;
int  root;    /*  根結點位置  */
int  num ;   /*  結點數   */ 
}Ptree ;

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

孩子鏈表表示法

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

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

⑶ 復合鏈表結構
（順序存儲+鏈式存儲）
具體辦法是：把所有結點放到1個順序存儲的數組中，然后將每一個結點的孩子結點排列起來，用單鏈表作存儲結構（由于每一個結點的孩子數不肯定）。

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

設計兩種結點結構：
表頭數組的表頭結點: (firstchild存儲該結點的孩子鏈表的頭指針）；
孩子鏈表的表結點：(childno用來存儲某個結點在表頭數組中的下標，next指向下1個孩子）。

數據結構類型定義

數據結構類型定義以下：

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

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

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

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

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

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

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

森林與2叉樹的轉換

     由于2叉樹和樹都可用2叉鏈表作為存儲結構，對照各自的結點結構可以看出，以2叉鏈表作為媒介可以導出樹和2叉樹之間的1個對應關系。

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

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

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

樹和森林的遍歷

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