樹結構是一種非線性存儲結構,存儲的是具有“一對多”關系的數據元素的集合。
樹型存儲結構類似于家族的族譜,各個結點之間也同樣可能具有父子、兄弟、表兄弟的關系。
A 和B、F、G 有關系; B 和 C、E 有關系。這就是“一對多”的關系。
整個存儲形狀在邏輯結構上看,類似于實際生活中倒着的樹,所以稱這種存儲結構為“樹型”存儲結構。
節點節點:使用樹結構存儲的每一個數據元素都被稱為“節點”。
根節點:每一個非空樹都有且隻有一個被稱為根的節點。
葉子節點:節點沒有任何子節點。
父節點、子節點:A為B、F、G的父節點,B、F、G為A的子節點。
兄弟節點:有相同的父節點
子樹和空樹空樹:如果集合本身為空,那麼構成的樹就被稱為空樹。空樹中沒有節點。
子樹:任何一個節點拆開來看,都是一個根節點,此時也是一棵樹。
備注:在樹結構中,對于具有同一個根節點的各個子樹,相互之間不能有交集。如果有,就破壞了樹的結構,不能算做是一棵樹。
度和層有序樹和無序樹
樹中節點的子樹從左到右看,誰在左邊,誰在右邊,是有規定的,這棵樹稱為有序樹;反之稱為無序樹。
在我們大多數的應用中都是有序樹。
森林樹可以理解為是由根節點和多個子樹構成,而這多個子樹本身是一個森林。
Tree(樹) =(root,F)
root 表示樹的根節點,F 表示由 m(m >= 0)棵樹組成的森林。
樹的表示方法廣義表、凹入表示法、嵌套的集合的形式表示。
,