樹概念及結構

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

注意：

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

如圖：

注意：

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

相關概念

如圖：

• 節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度； 如上圖：A的為6
• 葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點； 如上圖：B、C、H、I…等節(jié)點為葉節(jié)點
• 非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點； 如上圖：D、E、F、G…等節(jié)點為分支節(jié)點
• 雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；如上圖：A是B的父節(jié)點
• 孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點； 如上圖：B是A的孩子節(jié)點
• 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點； 如上圖：B、C是兄弟節(jié)點
• 樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度； 如上圖：樹的度為6
• 節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；
• 樹的高度或深度：樹中節(jié)點的最大層次； 如上圖：樹的高度為4
• 堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；如上圖：H、I互為兄弟節(jié)點
• 節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先
• 子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖：所有節(jié)點都是A的子孫 森林：由m（m>0）棵互不相交的樹的集合稱為森林；

樹的表示

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

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

如圖：

樹在實際中的運用（表示文件系統(tǒng)的目錄樹結構）

二叉樹概念及結構

概念

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

需要注意的特殊二叉樹

滿二叉樹：

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

完全二叉樹：

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

二叉樹的性質

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

二叉樹的存儲結構

存儲結構類型：

順序存儲

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

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

如圖：

鏈式存儲

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是
鏈表中每個結點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所
在的鏈結點的存儲地址 。

例：

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向當前節(jié)點左孩子
    struct BinTreeNode* _pRight; // 指向當前節(jié)點右孩子
    BTDataType _data; // 當前節(jié)點值域
}

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

總結

這只是二叉樹的基本知識，之后我們還會詳細解析二叉數(shù)的遞歸實現(xiàn)和有關題目。

到此這篇關于C語言深入淺出解析二叉樹的文章就介紹到這了,更多相關C語言 二叉樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論