第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

1. 前言

前面的章節(jié)我們介紹了兩種重要的數(shù)據(jù)結(jié)構(gòu)，數(shù)組和鏈表，由于他們各自的特性使得他們的優(yōu)缺點非常分明，在查詢速度和插入速度上顧此失彼，不能兼顧，那么有沒有一種數(shù)據(jù)結(jié)構(gòu)可以同時高效的完成插入和查詢操作呢，答案當(dāng)然是肯定的，今天我們就來了解 —— 樹結(jié)構(gòu)。

2. 樹的定義及常用概念

顧名思義，樹結(jié)構(gòu)就是以樹為原型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹形結(jié)構(gòu)的數(shù)據(jù)集合。大自然的鬼斧神工讓人不得不驚嘆它的神奇之力，如何最高效的為每一片葉子供給養(yǎng)分，同時還可以不斷的抽枝發(fā)芽分支出新的枝干，大樹為它的枝葉們提供了最科學(xué)的結(jié)構(gòu)基礎(chǔ)。而我們也仿照大自然中樹的結(jié)構(gòu)，構(gòu)建了計算機(jī)領(lǐng)域里的樹形結(jié)構(gòu)。下面我們先定義一些有關(guān)樹形結(jié)構(gòu)用到的概念。

• 節(jié)點：樹結(jié)構(gòu)中用于存儲數(shù)據(jù)元素的部分稱為節(jié)點。
• 根節(jié)點：我們的樹是倒掛的，因此最上面的節(jié)點我們稱之為根節(jié)點。
• 邊：連接元素之間的引用我們稱之為邊。邊是有方向的，從上游節(jié)點指向下游節(jié)點。
• 路徑：順著邊，將經(jīng)過的節(jié)點按順序記錄下來，稱之為路徑。路徑上節(jié)點的個數(shù)稱之為路徑的長度。
• 父節(jié)點：節(jié)點的上游節(jié)點稱之為父節(jié)點，通過指向某一節(jié)點的邊可以找到它的父節(jié)點。
• 子節(jié)點：節(jié)點的下游節(jié)點稱之為子節(jié)點，通過向下發(fā)出的邊可以找到它的子節(jié)點。
• 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點之間互稱為兄弟節(jié)點。
• 葉節(jié)點：沒有子節(jié)點的節(jié)點稱之為葉節(jié)點，它是樹在這個路徑上的末端。
• 層次：根節(jié)點為第一層，根的所有子節(jié)點為第二層，第二層的所有子節(jié)點組成第三層，以此類推。
• 深度：從根節(jié)點到某一個節(jié)點的路徑長度稱之為該節(jié)點的深度。根節(jié)點的深度為 0。
• 高度：從某一節(jié)點出發(fā)到最遠(yuǎn)的葉節(jié)點的路徑長度稱之為該節(jié)點的高度。葉節(jié)點的高度為 0。

3. 二叉樹

當(dāng)一個樹形結(jié)構(gòu)上的每個節(jié)點最多只有兩個子節(jié)點時，這個樹可以稱之為二叉樹。二叉樹根據(jù)節(jié)點和元素的分布又可以細(xì)分很多類型，比如：

• 滿二叉樹：除葉節(jié)點外，每一個節(jié)點都有兩個子節(jié)點。
• 完全二叉樹：當(dāng)我們從上至下，從左至右，按照二叉樹的結(jié)構(gòu)依次排滿每一個節(jié)點的時候，這個樹就是完全二叉樹，其中當(dāng)最下面一層的葉節(jié)點排滿時，這個完全二叉樹同時也是滿二叉樹。

• 二叉搜索樹：當(dāng)一個節(jié)點有左子節(jié)點時，左子樹上的所有節(jié)點一定小于它，同時當(dāng)一個節(jié)點有右子節(jié)點時，右子樹上的所有節(jié)點一定大于它，這個樹稱之為二叉搜索樹，或者二叉查找數(shù)。通過這個特殊的約定，我們得到了一個規(guī)律性很強(qiáng)的樹形結(jié)構(gòu)，給我們做進(jìn)一步的搜索查找提供了很大的便利。

4. 遍歷樹

對樹上節(jié)點的訪問順序其實是一樣的，但是輸出順序不同，根據(jù)輸出順序我們將遍歷分為三種：前序遍歷、中序遍歷、后序遍歷。

• 前序遍歷的規(guī)則是根節(jié)點 > 左子樹 > 右子樹；

• 中序遍歷的規(guī)則是左子樹 > 根節(jié)點 > 右子樹；

• 后序遍歷的規(guī)則是左子樹 > 右子樹 > 根節(jié)點；

5. 小結(jié)

本節(jié)我們學(xué)習(xí)了樹形結(jié)構(gòu)，我們要清晰掌握常用的概念，知道樹是由節(jié)點和邊構(gòu)成的一種抽象數(shù)據(jù)類型，了解二叉樹的定義和特點，知道二叉樹的每個節(jié)點最多有兩個子節(jié)點，說出幾種最常見的二叉樹類型比如滿二叉樹和完全二叉樹，了解當(dāng)二叉樹中任意一個節(jié)點下的左子樹的所有節(jié)點都比該節(jié)點小，右子樹的所有節(jié)點又都比該節(jié)點大時，這個樹稱之為二叉搜索樹。此外大家要根據(jù)前序遍歷、中序遍歷、后序遍歷的規(guī)則，結(jié)合動圖掌握二叉樹遍歷的思路和方法。