溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“C語言中二叉樹的示例分析”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“C語言中二叉樹的示例分析”這篇文章吧。
樹是一種 非線性 的數據結構，它是由 n （ n>=0 ）個有限結點組成一個具有層次關系的集合
把它叫做樹是因 為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的
注意：
有一個特殊的結點，稱為根結點，根節點沒有前驅結點
除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <=m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼 因此，樹是遞歸定義的。
如圖：
注意：
樹形結構中，子樹之間不能有交集，否則就不是樹形結構
除了根節點外，每個節點有且只有一個父節點
一棵樹N個節點的樹有N-1條邊
如圖：
節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6
葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點
非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；如上圖：A是B的父節點
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫 森林：由m（m>0）棵互不相交的樹的集合稱為森林；
樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間
的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法
等。我們這里就簡單的了解其中最常用的 孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個孩子結點
struct Node* _pNextBrother; // 指向其下一個兄弟結點
DataType _data; // 結點中的數據域
};如圖：
二叉樹由一個根節點加上左子樹和右子樹組成：
二叉樹度最大為2（度可以為0,1,2）
二叉樹的子樹有左右之分，次序不能顛倒（有序樹）（沒有左樹，一定沒有右樹；有左樹，不一定有右樹）
滿二叉樹：
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹
也就是說，如果一個二叉樹的層數為K，且結點總數是2^k-1，則它就是滿二叉樹
完全二叉樹：
完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的（特殊的完全二叉樹）
對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹
若規定根節點的層數為 1 ，則一棵非空二叉樹的 第 i 層上最多有2^（i-1）個結點
若規定根節點的層數為 1 ，則 深度為 h的二叉樹的最大結點數是2^h-1
若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h=log2（n+1）（是log以2為底，n+1為對數）
存儲結構類型：
順序結構存儲就是使用 數組來存儲 ，一般使用數組只適合表示完全二叉樹（不完全二叉樹有空間的浪費）而現實中使用中只有堆才會使用數組來存儲
注：二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹
如圖：
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是
鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所
在的鏈結點的存儲地址 。
例：
typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當前節點左孩子
struct BinTreeNode* _pRight; // 指向當前節點右孩子
BTDataType _data; // 當前節點值域
}// 三叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向當前節點的雙親
struct BinTreeNode* _pLeft; // 指向當前節點左孩子
struct BinTreeNode* _pRight; // 指向當前節點右孩子
BTDataType _data; // 當前節點值域
}；以上是“C語言中二叉樹的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
