目錄

1.雙親表示法

2.孩子鏈表

3.孩子兄弟表示法

4.樹(shù)與二叉樹(shù)的轉(zhuǎn)換

（1）樹(shù)轉(zhuǎn)換為二叉樹(shù)

（2）二叉樹(shù)轉(zhuǎn)換成樹(shù)

5.二叉樹(shù)與森林的轉(zhuǎn)化

（1）森林轉(zhuǎn)換為二叉樹(shù)

以下樹(shù)為例

1.雙親表示法

雙親表示法定義了一個(gè)結(jié)構(gòu)數(shù)組，存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域

數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息

雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組的位置

?如下圖所示A,B,C的父節(jié)點(diǎn)為R

2.孩子鏈表

#孩子結(jié)點(diǎn)結(jié)構(gòu)
typedef struct CTNode{int child;struct CTNode *next;
}*ChildPtr;#樹(shù)結(jié)構(gòu)
typedef struct{CTBox nodes[MAX_TREE_SIZE];int n,r;//n表示結(jié)點(diǎn)數(shù),r表示根結(jié)點(diǎn)的位置
}#雙親結(jié)點(diǎn)結(jié)構(gòu)
typedef struct{TElemType data;ChildPtr firstchild;}CTBox;

3.孩子兄弟表示法

用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)

typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;}CSNode,*CSTree;

如下圖“A”所示，第一個(gè)指針域指向他的第一個(gè)孩子“D”，第二個(gè)指針域指向他的兄弟結(jié)點(diǎn)B，以此類推:?

4.樹(shù)與二叉樹(shù)的轉(zhuǎn)換

樹(shù)的存儲(chǔ)結(jié)構(gòu)如上圖所示，第一個(gè)指針域指向第一個(gè)孩子，第二個(gè)指針域指向兄弟結(jié)點(diǎn)

而二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)則為第一個(gè)指針域指向左孩子，第二個(gè)指針域指向右孩子，轉(zhuǎn)換如下：

那轉(zhuǎn)換的方法是什么呢？

（1）樹(shù)轉(zhuǎn)換為二叉樹(shù)

?在兄弟之間加連線

?對(duì)于每一個(gè)結(jié)點(diǎn)，除了左孩子外，去掉其與其余孩子之間的關(guān)系

?以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45度

更復(fù)雜的可以看下圖：

（2）二叉樹(shù)轉(zhuǎn)換成樹(shù)

??若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子......沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)

?抹掉原二叉樹(shù)中雙親與右孩子之間的連線

?將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)

5.二叉樹(shù)與森林的轉(zhuǎn)化

（1）森林轉(zhuǎn)換為二叉樹(shù)

?將每一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)

?將每一個(gè)根結(jié)點(diǎn)連接起來(lái)

?旋轉(zhuǎn)45度

（2）二叉樹(shù)轉(zhuǎn)換為森林

?將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)

?將孤立的二又樹(shù)還原成樹(shù)