web開發(fā)中二叉樹的示例分析

這篇文章將為大家詳細講解有關(guān)web開發(fā)中二叉樹的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)長期為超過千家客戶提供的網(wǎng)站建設(shè)服務，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為托克遜企業(yè)提供專業(yè)的網(wǎng)站設(shè)計、網(wǎng)站建設(shè)，托克遜網(wǎng)站改版等技術(shù)服務。擁有十多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

0.  前言

到目前為止，我們已經(jīng)講述了順序表、鏈表、棧、隊列四種數(shù)據(jù)結(jié)構(gòu)，它們有一個共同的特點，就是它們都是線性表，換句話來說，它們都是線性結(jié)構(gòu)，像一根繩子一樣。

四種線性數(shù)據(jù)結(jié)構(gòu)

在文章【線性表】已經(jīng)介紹過線性表的定義了，即由若干元素按照線性結(jié)構(gòu)(一對一的關(guān)系)組成的有限序列。

關(guān)鍵詞是一對一的關(guān)系。

顯然，在復雜的現(xiàn)實社會中，這種一對一的關(guān)系是不能較好的滿足我們的需求的。

比如說，父母和多個孩子之間的關(guān)系，一個父親/母親對應多個孩子，這顯然不是一對一，而是一對多的關(guān)系。那么此時我們?nèi)绾蝸砻枋鲞@種一對多的關(guān)系呢?

當然是使用具有一對多關(guān)系的數(shù)據(jù)結(jié)構(gòu)啦!有這種數(shù)據(jù)結(jié)構(gòu)嗎?有!本文就來介紹這種數(shù)據(jù)結(jié)構(gòu) —— 樹及其特殊形式的二叉樹。

1. 識樹

1.0. 什么是樹?

提到樹(Tree)，大家腦海中首先浮出的畫面應該是類似這樣的：

圖片來自網(wǎng)絡(luò)

之所以我們會用“樹”這個名詞來命名具有“一對多關(guān)系”特性的數(shù)據(jù)結(jié)構(gòu)，是因為樹剛好能夠很形象地詮釋這種特性。我們來分析一下。

看一下上圖中的樹(土地以上的部分)，它有一個樹根，從樹根開始往上分叉，主樹干分叉成許多次樹干，次樹干又繼續(xù)分叉為許多小樹枝，小樹枝上有許多葉子……

主樹干對次樹干、次樹干對小樹枝、小樹枝對葉子都是一對多的關(guān)系，我們用圓圈代表樹干和葉子，把自然界的樹倒過來進行一次抽象，得下圖(為了方便起見，我們的數(shù)據(jù)全為字符類型)：

一棵樹

可以看到，現(xiàn)實中的樹完美契合我們需要的數(shù)據(jù)結(jié)構(gòu)，所以我們稱這種數(shù)據(jù)結(jié)構(gòu)為樹(Tree)。

1.1. 名詞與概念

我們按圖索驥，來認識樹的相關(guān)名詞。

子樹：樹是一個有限集合，子樹則是該集合的子集。就像套娃一樣，一棵樹下面還包含著其子樹。

比如，樹T1 的子樹為 樹T2、T3、T4，樹T2的子樹為 T5、T6. 上圖中還有許多子樹沒有標記出來。

結(jié)點(Node)：一個結(jié)點包括一個數(shù)據(jù)元素和若干指向其子樹分支。

比如，在樹T1 中，結(jié)點A 包括一個數(shù)據(jù)元素A 和 三個指向其子樹的分支。上圖中共有 17 個結(jié)點。

根結(jié)點(Root)：一顆樹只有一個樹根，這是常識。在數(shù)據(jù)結(jié)構(gòu)中，“樹根”即根節(jié)點。

比如，結(jié)點A 是樹 T1 的根結(jié)點;結(jié)點C 是樹T1 的子結(jié)點，是樹 T3 的根結(jié)點。

度(Degree)：一個結(jié)點擁有的子樹數(shù)。

比如，結(jié)點A 的度為 3，結(jié)點G 的度為 3，結(jié)點H 的度為 1.

葉子(Leaf)/ 終端結(jié)點：度為 0 的結(jié)點被稱為葉子結(jié)點，很形象吧。

比如，對于樹 T1來說，結(jié)點F、I、K、L、M、N、O、P、Q 均為葉子。

分支結(jié)點 / 非終端結(jié)點：和葉子結(jié)點相對，即度不為 0 的結(jié)點。

內(nèi)部結(jié)點：顧名思義，在樹內(nèi)部的結(jié)點，即不是根結(jié)點和葉子結(jié)點的結(jié)點。

孩子(Child)、雙親(Parent)、兄弟(Sibling)、堂兄弟、祖先、子孫這些概念和族譜上的相同。

比如，對于結(jié)點B 來說：結(jié)點A 是其雙親結(jié)點，結(jié)點E、F 是其孩子結(jié)點，結(jié)點C、D 是其兄弟結(jié)點，結(jié)點K 是其子孫結(jié)點。

層次(Level)：從根結(jié)點開始，根為第一次，根的孩子為第二層，依次往下。

比如，結(jié)點K 在樹 T1 中的層次為 4.

深度(Depth)/ 高度：指樹的最大層次。

比如，樹 T1 的深度為 4.

有序樹：如果結(jié)點的各子樹從左到右是有次序的、不能顛倒，則為有序樹，否則為無序樹。對于有序樹的孩子來說，最左邊的孩子稱為第一個孩子，最右邊的孩子稱為最后一個孩子。

比如，如果樹T1是一個有序樹，則其根結(jié)點的第一個孩子為結(jié)點B，最后一個孩子為結(jié)點D.

1.2. 樹的遞歸概念

前面已經(jīng)介紹了樹的輪廓和相關(guān)名詞概念，為了回答什么是樹這個問題，我們這里還需要介紹三種常見的樹結(jié)構(gòu)。

【空樹】：一顆空樹，即沒有結(jié)點的樹。

空樹

【只有根結(jié)點的樹】：只有一個根節(jié)點，沒有其他結(jié)點。

只有根結(jié)點的樹

【普通的樹】

普通樹

現(xiàn)在我們能來回答什么是樹了：

樹(Tree)是由 N (N >= 0) 個結(jié)點構(gòu)成的有限集合。

• 當 N = 0 時，樹為空樹

• 當 N = 1 時，樹只有一個根結(jié)點

• 當 N > 1 時，樹除了一個根結(jié)點外，其余結(jié)點又可分為若干個不相交的有限集合，我們稱之為子樹。

非空樹有且僅有一個根結(jié)點。

樹的一對多的關(guān)系存在于雙親結(jié)點和孩子結(jié)點之間。

在樹中，因為存在樹、子樹的概念，所以樹的子樹仍是一顆樹，子樹的子樹仍是一棵樹。

• 舉個例子：人類的孩子仍是人類，人類的孩子的孩子仍是人類。

因為存在雙親、孩子、子孫的概念，所以根結(jié)點的孩子結(jié)點可以其子樹的根結(jié)點。

• 舉個例子：一個人，在其孩子看來是父親，在其父母看來是兒子。

這種概念，就是遞歸的概念。

即，對于某個“事物”而言，它的“孩子”和它本身并無實質(zhì)區(qū)別，它做的事，它的“孩子”也會做、也要做。一直向下，“孫子”“曾孫”“玄孫”皆是如此。

為了說明遞歸這個概念，我們將上圖的樹遞歸地分解為子樹，下圖中每個區(qū)域都是一顆樹(或子樹)：

遞歸解樹

分解到最后，我們最終得到的，可以說是葉子結(jié)點，也可以說是只有根結(jié)點的樹。如結(jié)點F、K、L.

在分解的過程中，我們還可以發(fā)現(xiàn)，對于每個結(jié)點來說，我們都可以將其看作某棵樹(子樹)的根結(jié)點。比如結(jié)點E、I都是某棵子樹的根結(jié)點。這與樹有且只有一個根結(jié)點并不矛盾。

• 這就好比我們說，小明只能有一個親生父親，但不影響他成為別人的父親。

整個過程就像在族譜上從祖宗找到子孫一樣。所以如果對樹的概念有啥不了解的，可以找個族譜翻翻看。

到此，我們可以說，樹的定義是一個遞歸的定義，樹是由根結(jié)點和它的若干子樹組成的，子樹也是由根結(jié)點和它的若干子樹組成的……即在樹的定義中又用到樹的定義。

1.3. 樹和線性表的比較

比較

看圖直觀體驗何為(前驅(qū)結(jié)點和后繼結(jié)點間)一對一的關(guān)系，何為(雙親結(jié)點和孩子結(jié)點之間)一對多的關(guān)系。

2. 識二叉樹

2.0. 什么是二叉樹?

何為二叉樹?首先它得是顆樹，其次它得是二叉的。

前面已經(jīng)初步認識了樹，它的結(jié)點的孩子數(shù)量是沒有限制的，即，你想要幾個孩子就要幾個孩子，想分幾個叉就分幾個叉。

而二叉樹，則是限制了孩子數(shù)量，即每個結(jié)點最多只能有兩個孩子(左孩子和右孩子)，打個比方就是“二胎樹”。

二叉樹

結(jié)點A 的左孩子是結(jié)點B，右孩子是結(jié)點C.

二叉樹是一種每個結(jié)點至多有兩棵子樹(即每個結(jié)點的度最大為 2 )的有序樹。

2.1. 二叉樹的幾種形態(tài)

一、空二叉樹

二、僅有根結(jié)點的二叉樹

三、左子樹為空的二叉樹

四、右子樹為空的二叉樹

五、左右子樹都不為空的二叉樹

2.2. 滿二叉樹和完全二叉樹

滿二叉樹的特點在于“滿”，即每層的結(jié)點數(shù)都是最大結(jié)點數(shù)。

滿二叉樹

T2 的第 3 層次沒有達到最大結(jié)點數(shù)，缺了 1 個;T3 的第 4 層次沒有達到最大結(jié)點數(shù)，缺了 7 個。

完全二叉樹是相對于滿二叉樹來說的，見下圖：

紅色部分為編號

二叉樹是有序樹，對一顆滿二叉樹和一顆完全二叉樹按「自上向下，自左向右」的順序進行編號，如上圖。

完全二叉樹中的所有結(jié)點的編號必須和滿二叉樹的相同編號的結(jié)點在位置上完全相同。

換句話說，完全二叉樹的結(jié)點按「自上向下，自左向右」的順序不能中斷。T3 的結(jié)點C 沒有左孩子，顯然按那個順序是中斷的。

3. 二叉樹的遍歷

3.0.  如何遍歷?

在線性表中，我們的遍歷非常簡單粗暴，找到線性表頭，使用循環(huán)直接一股腦的到線性表尾，即完成遍歷了。在樹中，我們不能在做這么簡單粗暴的事了，因為樹是一對多的關(guān)系，所以從頭到尾的遍歷是不可能的。

遍歷的實質(zhì)是，將線性排列的元素順序打印出來。(遍歷不止干打印的事，為了方便起見，我們的遍歷是打印元素)

而遍歷樹的矛盾在于，我們的樹不是線性的，為了解決這個矛盾，我們可不可以約定好某種順序，將樹的元素按這種順序線性排列起來，然后遍歷就是從頭到尾的簡單粗暴之事了?答案是可以的。

我們知道樹是遞歸的定義，二叉樹是由根結(jié)點、左子樹、右子樹這三部分遞歸地組合而成的。 所以我們要約定的就是這三部分誰先誰后。

按照人們寫字先左后右的約定，我們也約定先左子樹后右子樹的順序(當然你可以先右后左)，那么根結(jié)點就只有三個位置可以放了。

根結(jié)點 >> 左子樹 >> 右子樹，稱為先序(根)遍歷

左子樹 >> 根結(jié)點 >> 右子樹，稱為中序(根)遍歷

左子樹 >> 右子樹 >> 根結(jié)點，稱為后序(根)遍歷

約定好之后，只需要按照順序遞歸地來就好了，就像找族譜一樣。

下面以遍歷下圖二叉樹為例：

為了方便起見，我們將 null 畫出來，且將所有子樹用顏色標志出來。

3.1. 先序遍歷

先序遍歷的遞歸描述如下：

若二叉樹為空，則空操作;否則：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 訪問根結(jié)點

3. 先序遍歷左子樹

4. 先序遍歷右子樹

你可能會問，怎么只有訪問根結(jié)點這一步?左孩子和右孩子結(jié)點呢?前面說過一句話：對于每個結(jié)點來說，我們都可以將其看作某棵樹(子樹)的根結(jié)點。就像你的兒子會成為別人的父親一樣。所以只要遞歸地訪問根結(jié)點，將每個結(jié)點遞歸地變?yōu)椤案Y(jié)點”，我們就能完成遍歷。

所以與其說是在遍歷結(jié)點，不如說是在遍歷「根結(jié)點」，我們只是在遞歸地把「所有根結(jié)點」找出來并輸出而已。(因為每個結(jié)點都可以看做是根結(jié)點)

所以遍歷的重點，在于將所有結(jié)點轉(zhuǎn)化為根結(jié)點看待，又因為每棵樹有且僅有一個根結(jié)點，所以我們要不斷地遞歸分解子樹(先左子樹后右子樹)，直到分解到  NULL為止。

過程如下：

先序遍歷的順序為：A B D E G C F

如果你感覺文字描述不直觀，可以在我以前寫過的文章中找到二叉樹遍歷過程的動態(tài)圖[1]。

3.2. 中序遍歷

中序遍歷的遞歸描述如下：

若二叉樹為空，則空操作;否則：

中序遍歷左子樹

訪問根結(jié)點

中序遍歷右子樹

過程如下：

中序遍歷的順序為：D B G E A C F

3.3. 后序遍歷

后序遍歷的遞歸描述如下：

若二叉樹為空，則空操作;否則：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 后序遍歷左子樹

3. 后序遍歷右子樹

4. 訪問根結(jié)點

過程不再描述，后序遍歷的順序為：D G E B F C A

關(guān)于“web開發(fā)中二叉樹的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

分享文章：web開發(fā)中二叉樹的示例分析
瀏覽路徑：http://bm7419.com/article10/iicogo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標簽優(yōu)化、定制網(wǎng)站、ChatGPT、小程序開發(fā)、服務器托管、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)