快捷導(dǎo)航

C語(yǔ)言深入淺出解析二叉樹(shù)

更新時(shí)間：2022年03月30日 15:53:14 作者：雪芙花

二叉樹(shù)可以簡(jiǎn)單理解為對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，最多擁有一個(gè)上級(jí)節(jié)點(diǎn)，同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。本文將詳細(xì)介紹一下C++中二叉樹(shù)的實(shí)現(xiàn)和遍歷，需要的可以參考一下

樹(shù)概念及結(jié)構(gòu)

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

注意：

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

如圖：

在這里插入圖片描述

注意：

樹(shù)形結(jié)構(gòu)中，子樹(shù)之間不能有交集，否則就不是樹(shù)形結(jié)構(gòu)
除了根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)
一棵樹(shù)N個(gè)節(jié)點(diǎn)的樹(shù)有N-1條邊

樹(shù)的表示

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

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ù)域
};

如圖：

在這里插入圖片描述

樹(shù)在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹(shù)結(jié)構(gòu)）

在這里插入圖片描述

二叉樹(shù)概念及結(jié)構(gòu)

概念

二叉樹(shù)由一個(gè)根節(jié)點(diǎn)加上左子樹(shù)和右子樹(shù)組成：
二叉樹(shù)度最大為2（度可以為0,1,2）
二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒（有序樹(shù)）（沒(méi)有左樹(shù)，一定沒(méi)有右樹(shù)；有左樹(shù)，不一定有右樹(shù)）

在這里插入圖片描述

需要注意的特殊二叉樹(shù)

滿(mǎn)二叉樹(shù)：

一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿(mǎn)二叉樹(shù)
也就是說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k-1，則它就是滿(mǎn)二叉樹(shù)

完全二叉樹(shù)：

完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的（特殊的完全二叉樹(shù)）
對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)

二叉樹(shù)的性質(zhì)

若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，則一棵非空二叉樹(shù)的第 i 層上最多有2^（i-1）個(gè)結(jié)點(diǎn)
若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，則深度為 h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^h-1
若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度，h=log2（n+1）（是log以2為底，n+1為對(duì)數(shù)）

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

存儲(chǔ)結(jié)構(gòu)類(lèi)型：

順序存儲(chǔ)

順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來(lái)存儲(chǔ) ，一般使用數(shù)組只適合表示完全二叉樹(shù)（不完全二叉樹(shù)有空間的浪費(fèi)）而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來(lái)存儲(chǔ)

注：二叉樹(shù)順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹(shù)

如圖：

在這里插入圖片描述

鏈?zhǔn)酱鎯?chǔ)

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。通常的方法是
鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所
在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。

例：

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)值域
}；