在大部分OJ題目中，節(jié)點(diǎn)個(gè)數(shù)
n作為參數(shù)傳入划栓。所以溪厘，比較適合使用采用一組連續(xù)的空間來存儲(chǔ)每個(gè)結(jié)點(diǎn)，即Node nodes[n]合搅。
1. 多叉樹表示法
1.1 雙親表示法
-
表格表示
-
參考代碼
struct Node{ char data; int parent; }; Node nodes[n]; 優(yōu)缺點(diǎn)
比較容易找到雙親多搀，但是不容易找到孩子。
2.2 孩子表示法
-
表格表示
-
參考代碼
struct Node{ char data; vector<int> children; }; Node nodes[n]; 優(yōu)缺點(diǎn)
比較容易找到孩子灾部，但是不容易找到雙親康铭。
優(yōu)化：雙親孩子表示法
-
表格表示
- 參考代碼
struct Node{ char data; int parent; vector<int> children; }; Node nodes[n]; - 優(yōu)缺點(diǎn)
雙親孩子都比較容易找到。
1.3 孩子兄弟表示法
-
表格表示
- 參考代碼
struct Node{ char data; int firstchild; int rightsib; }; Node nodes[n]; - 優(yōu)缺點(diǎn)
比較容易找到孩子和兄弟赌髓，但是不容易找到雙親从藤。
孩子兄弟表示法主要用來把多叉樹轉(zhuǎn)化成二叉樹。
練習(xí)
顯示樹結(jié)構(gòu)GraphvizOnline
graph G {
A--B
A--C
B--D
C--E
C--F
D--G
D--H
D--I
E--J
}
2 二叉樹表示法
2.1 順序存儲(chǔ)方式
將二叉樹存儲(chǔ)在一個(gè)數(shù)組中锁蠕，通過存儲(chǔ)元素的下標(biāo)反映元素之間的父子關(guān)系夷野。用一組連續(xù)地址的存儲(chǔ)空間依次自上而下、自左到右存儲(chǔ)二叉樹上的節(jié)點(diǎn)荣倾。
- 一棵深度為
的二叉樹通常需要
個(gè)節(jié)點(diǎn)空間存儲(chǔ)悯搔。
- 節(jié)點(diǎn)之間的關(guān)系根據(jù)二叉樹的性質(zhì)5確定。
| No. | 節(jié)點(diǎn) | 下標(biāo) |
|---|---|---|
| 1 | 根節(jié)點(diǎn) | |
| 2 | 葉子節(jié)點(diǎn) |
|
| 3 | 節(jié)點(diǎn) |
|
| 4 | 節(jié)點(diǎn) |
|
| 5 | 節(jié)點(diǎn) |
- 通常使用
0表示空節(jié)點(diǎn)舌仍。
結(jié)點(diǎn)個(gè)數(shù)已知的完全二叉樹或接近完全二叉樹的二叉樹妒貌，通常使用這種方式者娱。最壞情況為深度為且只有
個(gè)節(jié)點(diǎn)的單支數(shù)。
2.2 鏈?zhǔn)酱鎯?chǔ)方式
因?yàn)轫樞虼鎯?chǔ)存在的局限性苏揣，二叉樹比較常見的是鏈?zhǔn)酱鎯?chǔ)方式。由于二叉樹結(jié)構(gòu)簡(jiǎn)單推姻，通常使用孩子表示法平匈，或者孩子雙親表示法。
二叉樹的二叉鏈表.png
- 孩子表示法
struct Node{ char data; struct Node* right_child; struct Node*left_child; }; Node* head; - 孩子雙親表示法
struct Node{ char data; struct Node* right_child; struct Node* left_child; struct Node* parent; }; Node* head;
