-
樹形結構
鎖定
樹形結構是一層次的嵌套結構。一個樹形結構的外層和內層有相似的結構,所以這種結構多可以遞歸的表示。經典數據結構中的各種樹狀圖是一種典型的樹形結構:一棵樹可以簡單的表示為根,左子樹,右子樹。左子樹和右子樹又有自己的子樹。
- 中文名
- 樹形結構
- 外文名
- Tree Structure
- 關 係
- 一對多
- 節 點
- 可以是多個
- 結 構
- 非線性結構
樹形結構綜述
在樹形結構中,樹根結點沒有前驅結點,其餘每個結點有且只有一個前驅結點。葉子結點沒有後續結點,其餘每個結點的後續節點數可以是一個也可以是多個。
另外,數學統計中的樹形結構可表示層次關係。
樹形結構在其他許多方面也有應用。可表示從屬關係、並列關係。
樹形結構網站樹形結構
樹形結構基本性質
1、樹是n(n≥0)個結點的有限集。
2、在任意一個空樹中。
樹形結構相關術語
1、結點(Node):表示樹中的數據元素,由數據項和數據元素之間的關係組成。在圖中,共有10個結點。
2、結點的度(Degree of Node):結點所擁有的子樹的個數,在圖中,結點A的度為3。
3、樹的度(Degree of Tree):樹中各結點度的最大值。在圖5.1中,樹的度為3。
4、葉子結點(Leaf Node):度為0的結點,也叫終端結點。在圖5.1中,結點E、F、G、H、I、J都是葉子結點。
5、分支結點(Branch Node):度不為0的結點,也叫非終端結點或內部結點。在圖5.1中,結點A、B、C、D是分支結點。
6、孩子(Child):結點子樹的根。在圖中,結點B、C、D是結點A的孩子。
7、雙親(Parent):結點的上層結點叫該結點的雙親。在圖中,結點B、C、D的雙親是結點A。
8、祖先(Ancestor):從根到該結點所經分支上的所有結點。在圖中,結點E的祖先是A和B。
9、子孫(Descendant):以某結點為根的子樹中的任一結點。在圖中,除A之外的所有結點都是A的子孫。
10、兄弟(Brother):同一雙親的孩子。在圖5.1中,結點B、C、D互為兄弟。
12、堂兄弟(Sibling):同一層的雙親不同的結點。在圖中,G和H互為堂兄弟。
16、森林(Forest):m(m≥0)棵樹的集合。自然界中的樹和森林的概念差別很大,但在數據結構中樹和森林的概念差別很小。從定義可知,一棵樹由根結點和m個子樹構成,若把樹的根結點刪除,則樹變成了包含m棵樹的森林。當然,根據定義,一棵樹也可以稱為森林。
[1]
- 參考資料
-
- 1. 數據結構_樹形結構 .博客園[引用日期2015-01-22]