數據結構中樹的基本定義相關概念匯總

定義

樹的遞歸定義如下(個人比較喜歡的定義，源自百度百科)：

設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱T1,T2,..,Tk為結點n的子樹。

空集合也是樹，稱為空樹?？諛渲袥]有結點。

相關術語(源自維基百科,有改動)

1、節點的度：一個節點含有的子樹的個數稱為該節點的度；
2、樹的度：一棵樹中所有節點的度的最大值稱為樹的度；
3、葉節點或終端節點：度為零的節點；
4、非終端節點或分支節點：度不為零的節點；

5、父親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
6、孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
7、兄弟節點：具有相同父節點的節點互稱為兄弟節點；

8、節點的層次：定義一棵樹的根節點層次為1，其他節點的層次是其父節點層次加1；
9、樹的高度或深度：一棵樹中所有節點的層次的最大值稱為這棵樹的深度；

10、堂兄弟節點：父節點在同一層的節點互為堂兄弟；
11、節點的祖先：從根到該節點所經分支上的所有節點；
12、子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
13、森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

需要說明下：節點＝結點，都源自英文單詞node。葉節點＝葉子節點

種類

無序樹：樹中任意節點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹;
有序樹：樹中任意節點的子結點之間有順序關系，這種樹稱為有序樹；

二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
二叉查找樹（二叉排序樹）
完全二叉樹
滿二叉樹
平衡二叉樹
霍夫曼樹：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；

紅黑樹
B樹

表示方法

最直觀的是樹形表示法

還有另一個常用的方法：先將根結點放入一對圓括號中，根結點后緊跟一對圓括號，然后把它的子樹按從左至右的順序放入該括號中，同層子樹之間用逗號隔開。如前文樹形表示法可以表示為：（1（2（4），3（5，6）））

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈