數(shù)據(jù)結(jié)構(gòu)_樹(shù)的基本概念

樹(shù)結(jié)構(gòu)是一種非線性存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)得是具有“一對(duì)多”關(guān)系得數(shù)據(jù)元素得集合。

樹(shù)型存儲(chǔ)結(jié)構(gòu)類(lèi)似于家族得族譜，各個(gè)結(jié)點(diǎn)之間也同樣可能具有父子、兄弟、表兄弟得關(guān)系。

A 和B、F、G 有關(guān)系； B 和 C、E 有關(guān)系。這就是“一對(duì)多”得關(guān)系。

整個(gè)存儲(chǔ)形狀在邏輯結(jié)構(gòu)上看，類(lèi)似于實(shí)際生活中倒著得樹(shù)，所以稱這種存儲(chǔ)結(jié)構(gòu)為“樹(shù)型”存儲(chǔ)結(jié)構(gòu)。

節(jié)點(diǎn)：使用樹(shù)結(jié)構(gòu)存儲(chǔ)得每一個(gè)數(shù)據(jù)元素都被稱為“節(jié)點(diǎn)”。

根節(jié)點(diǎn)：每一個(gè)非空樹(shù)都有且只有一個(gè)被稱為根得節(jié)點(diǎn)。

葉子節(jié)點(diǎn)：節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)。

父節(jié)點(diǎn)、子節(jié)點(diǎn)：A為B、F、G得父節(jié)點(diǎn)，B、F、G為A得子節(jié)點(diǎn)。

兄弟節(jié)點(diǎn)：有相同得父節(jié)點(diǎn)

空樹(shù)：如果集合本身為空，那么構(gòu)成得樹(shù)就被稱為空樹(shù)。空樹(shù)中沒(méi)有節(jié)點(diǎn)。

子樹(shù)：任何一個(gè)節(jié)點(diǎn)拆開(kāi)來(lái)看，都是一個(gè)根節(jié)點(diǎn)，此時(shí)也是一棵樹(shù)。

備注：在樹(shù)結(jié)構(gòu)中，對(duì)于具有同一個(gè)根節(jié)點(diǎn)得各個(gè)子樹(shù)，相互之間不能有交集。如果有，就破壞了樹(shù)得結(jié)構(gòu)，不能算做是一棵樹(shù)。

樹(shù)中節(jié)點(diǎn)得子樹(shù)從左到右看，誰(shuí)在左邊，誰(shuí)在右邊，是有規(guī)定得，這棵樹(shù)稱為有序樹(shù)；反之稱為無(wú)序樹(shù)。

在我們大多數(shù)得應(yīng)用中都是有序樹(shù)。

樹(shù)可以理解為是由根節(jié)點(diǎn)和多個(gè)子樹(shù)構(gòu)成，而這多個(gè)子樹(shù)本身是一個(gè)森林。

Tree(樹(shù)) =（root,F）

root 表示樹(shù)得根節(jié)點(diǎn)，F(xiàn) 表示由 m（m >= 0）棵樹(shù)組成得森林。

廣義表、凹入表示法、嵌套得集合得形式表示。