?

?

??個(gè)人主頁：guoguoqiang. ??專欄：數(shù)據(jù)結(jié)構(gòu)

?

一、樹的基本概念

1.概念

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

在樹中，子樹不能有交集，不然就是圖。

?節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(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)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(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)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
樹的高度或深度：樹中節(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）棵互不相交的樹的集合稱為森林；

2.樹的表示

樹的表示通常是通過左孩子右兄弟來表示的。
parent=(child-1)/2;
左孩子=2parent+1;
右孩子=2parent+2;

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個(gè)孩子結(jié)點(diǎn)
struct Node* _pNextBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn)
DataType _data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

3.樹在實(shí)際中的應(yīng)用

二、二叉樹的概念及結(jié)構(gòu)

1.二叉樹的概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合:

1. 或者為空
2. 由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成
   二叉樹是有序樹 左子樹右子樹不能顛倒，二叉樹的度不能大于2.
   
   有兩種特殊的二叉樹：

1. 滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是
   說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K
   的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對
   應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

2.二叉樹的性質(zhì)

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2^(i-1)個(gè)結(jié)點(diǎn).
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h-1 .
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n0 , 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有 n0＝n2 ＋1
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h=log2(n+1) (ps：是log以2為底，n+1為對數(shù))
5. 對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對
   于序號(hào)為i的結(jié)點(diǎn)有：
   1. 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無雙親節(jié)點(diǎn)
   2. 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無左孩子
   3. 若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無右孩子
6. 某二叉樹共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ B）
   A 不存在這樣的二叉樹
   B 200
   C 198
   D 199
   2.下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲(chǔ)結(jié)構(gòu)的是（A ）
   A 非完全二叉樹
   B 堆
   C 隊(duì)列
   D 棧
   3.在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（A ）//n0+n2=2n n0=n2+1
   A n
   B n+1
   C n-1
   D n/2
   4.一棵完全二叉樹的節(jié)點(diǎn)數(shù)位為531個(gè)，那么這棵樹的高度為（B ）//log2 512=9;
   A 11
   B 10
   C 8
   D 12
   5.一個(gè)具有767個(gè)節(jié)點(diǎn)的完全二叉樹，其葉子節(jié)點(diǎn)個(gè)數(shù)為（B）//n0+n1+n2=767 2n0-1+n1=767
   A 383
   B 384
   C 385
   D 386

3.二叉樹的存儲(chǔ)結(jié)構(gòu)

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

1. 順序存儲(chǔ)
   順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空
   間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來存儲(chǔ)，關(guān)于堆我們后面的章節(jié)會(huì)專門講解。二叉樹順
   序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。
   parent=(child-1)/2;
   左孩子=2parent+1;
   右孩子=2parent+2;
   通過上述公式構(gòu)建二叉樹。
   
2. 鏈?zhǔn)酱鎯?chǔ)
   二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是
   鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所
   在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈
   
   

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}
// 三叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親
struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}；

本篇內(nèi)容到此結(jié)束，感謝大家觀看！文章來源地址http://www.zghlxwxcb.cn/news/detail-851046.html

到了這里，關(guān)于愛上數(shù)據(jù)結(jié)構(gòu)：二叉樹的基本概念的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！