1.樹概念及結(jié)構(gòu)

1.1樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做樹是因 為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

補(bǔ)充： 

有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個前驅(qū)，可以有0個或多個后繼。因此，樹是遞歸定義的。

 1.2 樹的相關(guān)概念

節(jié)點(diǎn)的度：一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I...等節(jié)點(diǎn)為葉節(jié)點(diǎn)

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G...等節(jié)點(diǎn)為分支節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)（親兄弟）； 如上圖：B、C是兄弟節(jié)點(diǎn)

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4

堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林；（后面學(xué)習(xí)的并查集就是一顆森林）

我們必須了解這些概念，因為我們后面做題會問怎么求這些。比如：求二叉樹的深度

1.3 樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間 的關(guān)系，實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

代碼表示 

畫圖表示

2.二叉樹概念及結(jié)構(gòu)   

2.1概念

一棵二叉樹是結(jié)點(diǎn)的一個有限集合：

1. 或者為空

2. 由一個根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成

圖來！??！

 從上圖可以看出：

    1. 二叉樹不存在度大于2的結(jié)點(diǎn)

    2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

2.2 特殊的二叉樹

滿二叉樹和完全二叉樹介紹

2.3 二叉樹的性質(zhì) 

2.4 簡單二叉樹題目練習(xí) 

2.4.1

運(yùn)用性質(zhì)3秒解

2.4.2

我們觀察這個完全二叉樹，可以得出二叉樹最多存在三個度，度為0、1、2。而且度為1的只可能有兩個取值0或1

這時我們可以利用性質(zhì)3，將n2用n0表示，這樣就可以算出葉子節(jié)點(diǎn)個數(shù)（也就是度為0的節(jié)點(diǎn)個數(shù)）

2.4.3

高度為h的完全二叉樹節(jié)點(diǎn)范圍是多少呢？

最小值：當(dāng)?shù)趆層只有一個節(jié)點(diǎn)的時候（為什么要有一個節(jié)點(diǎn)呢，因為題目說的是完全二叉樹，如果第h層沒有節(jié)點(diǎn)的話就是h-1層的滿二叉樹了）

2.4.4

2.5 二叉樹的存儲結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

2.5.1 順序存儲——堆

順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。 

順序存儲邏輯圖

順序存儲結(jié)構(gòu)只適用于完全二叉樹和滿二叉樹，用數(shù)組的方式存儲，可以計算父子之間的下標(biāo)關(guān)系

不是完全二叉樹和滿二叉樹，就會出現(xiàn)下面的問題，有空間的浪費(fèi)（不適合），下面的鏈?zhǔn)酱鎯Y(jié)構(gòu)更適合這種二叉樹

2.5.2 鏈?zhǔn)酱鎯?/h4>

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點(diǎn)由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所 在的鏈結(jié)點(diǎn)的存儲地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。

二叉鏈和三叉鏈

如果覺得文章不錯，期待你的一鍵三連哦，你個鼓勵是我創(chuàng)作的動力之源，讓我們一起加油，頂峰相見?。?！

以上就是深入探究C語言中的二叉樹的詳細(xì)內(nèi)容，更多關(guān)于C語言 二叉樹的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

• C語言之平衡二叉樹詳解
• C語言之二叉樹的遍歷
• C語言進(jìn)階二叉樹的基礎(chǔ)與銷毀及層序遍歷詳解
• C語言進(jìn)階練習(xí)二叉樹的遞歸遍歷
• C語言堆與二叉樹的順序結(jié)構(gòu)與實(shí)現(xiàn)
• C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸

最新評論