通俗易懂講解二叉搜索樹

01-31

樹是一種非線性數據結構，其概念也不少。大家在初次接觸樹的時候，可能覺得它很難；之所產生這種感覺主要是由於樹有一大堆陌生的概念、性質等內容。而當我真正的實現了二叉樹再回過頭來看它的相關概念和性質的時候，覺得原來它是如此的簡單！

因此，建議在學習二叉樹的時候：先對二叉樹基本的概念、性質有個基本了解，遇到難懂的知識點，可以畫圖來幫助理解；在有個基本的概念之後，再親自動手實現二叉查找樹(這一點至關重要!)；最後再回過頭來總結一下二叉樹的理論知識時，你會發現其實一點不難！

這篇文章主要講各種樹的性質和定義。

樹的介紹

樹的定義

樹是一種數據結構，它是由n（n>=0）個有限節點組成一個具有層次關係的集合，把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個節點有零個或多個子節點；
沒有父節點的節點稱為根節點；
每一個非根節點有且只有一個父節點；
除了根節點外，每個子節點可以分為多個不相交的子樹。

樹的基本術語

若一個結點有子樹，那麼該結點稱為子樹根的"雙親"，子樹的根是該結點的"孩子"。有相同雙親的結點互為"兄弟"。一個結點的所有子樹上的任何結點都是該結點的後裔。從根結點到某個結點的路徑上的所有結點都是該結點的祖先，以下圖為例：

結點的度：結點擁有的子樹的數目，圖中結點c的度為2。葉子：度為零的結點，圖中D、E、F都是葉子結點 樹的度：樹中結點的最大的度，圖中結點c的度最大為2，因此樹的度為2。

層次：根結點的層次為1，其餘結點的層次等於該結點的雙親結點的層次加1。 樹的高度：樹中結點的最大層次，圖中樹的高度為3。 無序樹：如果樹中結點的各子樹之間的次序是不重要的，可以交換位置。 有序樹：如果樹中結點的各子樹之間的次序是重要的, 不可以交換位置。森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。