快捷導(dǎo)航

C語言深入淺出解析二叉樹

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

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

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

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

注意：

有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(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)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼因此，樹是遞歸定義的。

如圖：

在這里插入圖片描述

注意：

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

樹的表示

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

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í)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹結(jié)構(gòu)）

在這里插入圖片描述

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

概念

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

在這里插入圖片描述

需要注意的特殊二叉樹

滿二叉樹：

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

完全二叉樹：

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

二叉樹的性質(zhì)

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

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

存儲結(jié)構(gòu)類型：

順序存儲

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

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

如圖：

在這里插入圖片描述

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

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

例：

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