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