Adslv ·1. 前言
前面的章節我們介紹了兩種重要的數據結構，數組和鏈表，由于他們各自的特性使得他們的優缺點非常分明，在查詢速度和插入速度上顧此失彼，不能兼顧，那么有沒有一種數據結構可以同時高效的完成插入和查詢操作呢，答案當然是肯定的，今天我們就來了解 —— 樹結構。
2. 樹的定義及常用概念
顧名思義，樹結構就是以樹為原型的數據結構，用來模擬具有樹形結構的數據集合。大自然的鬼斧神工讓人不得不驚嘆它的神奇之力，如何最高效的為每一片葉子供給養分，同時還可以不斷的抽枝發芽分支出新的枝干，大樹為它的枝葉們提供了最科學的結構基礎。而我們也仿照大自然中樹的結構，構建了計算機領域里的樹形結構。下面我們先定義一些有關樹形結構用到的概念。
- 節點：樹結構中用于存儲數據元素的部分稱為節點。
- 根節點：我們的樹是倒掛的，因此最上面的節點我們稱之為根節點。
- 邊：連接元素之間的引用我們稱之為邊。邊是有方向的，從上游節點指向下游節點。
- 路徑：順著邊，將經過的節點按順序記錄下來，稱之為路徑。路徑上節點的個數稱之為路徑的長度。
- 父節點：節點的上游節點稱之為父節點，通過指向某一節點的邊可以找到它的父節點。
- 子節點：節點的下游節點稱之為子節點，通過向下發出的邊可以找到它的子節點。
- 兄弟節點：具有相同父節點的節點之間互稱為兄弟節點。
- 葉節點：沒有子節點的節點稱之為葉節點，它是樹在這個路徑上的末端。
- 層次：根節點為第一層，根的所有子節點為第二層，第二層的所有子節點組成第三層，以此類推。
- 深度：從根節點到某一個節點的路徑長度稱之為該節點的深度。根節點的深度為 0。
- 高度：從某一節點出發到最遠的葉節點的路徑長度稱之為該節點的高度。葉節點的高度為 0。
3. 二叉樹
當一個樹形結構上的每個節點最多只有兩個子節點時，這個樹可以稱之為二叉樹。二叉樹根據節點和元素的分布又可以細分很多類型，比如：
- 滿二叉樹：除葉節點外，每一個節點都有兩個子節點。
- 完全二叉樹：當我們從上至下，從左至右，按照二叉樹的結構依次排滿每一個節點的時候，這個樹就是完全二叉樹，其中當最下面一層的葉節點排滿時，這個完全二叉樹同時也是滿二叉樹。
- 二叉搜索樹：當一個節點有左子節點時，左子樹上的所有節點一定小于它，同時當一個節點有右子節點時，右子樹上的所有節點一定大于它，這個樹稱之為二叉搜索樹，或者二叉查找數。通過這個特殊的約定，我們得到了一個規律性很強的樹形結構，給我們做進一步的搜索查找提供了很大的便利。
4. 遍歷樹
對樹上節點的訪問順序其實是一樣的，但是輸出順序不同，根據輸出順序我們將遍歷分為三種：前序遍歷、中序遍歷、后序遍歷。
- 前序遍歷的規則是根節點 > 左子樹 > 右子樹；
- 中序遍歷的規則是左子樹 > 根節點 > 右子樹；
- 后序遍歷的規則是左子樹 > 右子樹 > 根節點；
5. 小結
本節我們學習了樹形結構，我們要清晰掌握常用的概念，知道樹是由節點和邊構成的一種抽象數據類型，了解二叉樹的定義和特點，知道二叉樹的每個節點最多有兩個子節點，說出幾種最常見的二叉樹類型比如滿二叉樹和完全二叉樹，了解當二叉樹中任意一個節點下的左子樹的所有節點都比該節點小，右子樹的所有節點又都比該節點大時，這個樹稱之為二叉搜索樹。此外大家要根據前序遍歷、中序遍歷、后序遍歷的規則，結合動圖掌握二叉樹遍歷的思路和方法。
2025 imooc.com All Rights Reserved |