溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“C++樹與二叉樹實例分析”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++樹與二叉樹實例分析”文章吧。
Q：什么是樹
A：樹是一種 非線性 的數據結構，它是由 n （ n>=0 ）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
Q：樹有什么特點
有一個特殊的結點，稱為根結點，根節點沒有前驅結點。
除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼。
樹是遞歸定義的
對于樹的定義還需要強調兩點：
當n>0時，根結點是唯一的，不可能存在多個根結點。數據結構中的樹是只能有一個根結點。
當m>0時，子樹的個數沒有限制，但它們一定是互不相交的。像下圖中的結構就不符合樹的定義，因為它們都有相交的子樹。
節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為3
葉節點：度為0的節點稱為葉節點； 如上圖：I,G,K,G,L,M節點為葉節點
非終端節點或分支節點：度不為0的節點； 如上圖：B、D、C、E、F等節點為分支節點
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為3
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推
樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫
森林：由m棵互不相交的樹的集合稱為森林
說到存儲結構，自然就會想到我們前面講過的順序存儲和鏈式存儲兩種結構。
順序存儲結構：樹中某個結點的孩子可以有多個，若將樹中所有結點存儲到數組中，結點的存儲位置無法直接反應其邏輯關系，因此：簡單的順序存儲結構是不能滿足樹的實現要求的
鏈式存儲結構：鏈式存儲結構的特點，完全可以實現對樹的存儲結構的表示。
表示方式：實際中樹有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。
代碼演示
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個孩子結點
struct Node* _pNextBrother; // 指向其下一個兄弟結點
DataType _data; // 結點中的數據域
};圖像演示
Q：什么是二叉樹
A：二叉樹是 n 個結點的有限集合。該集合或者為空集(空二叉樹)或者由一個根結點和兩棵互不相交的，分別稱為根結點的左子樹和右子樹的二叉樹組成。
Q：二叉樹有什么特點
每個結點最多有兩棵子樹，二叉樹不存在度大于2的結點。左子樹和右子樹是有順序的，次序不能任意顛倒。即使樹中某結點只有一棵子樹，也要區分左子樹還是右子樹。
Q：二叉樹有什么基本形式
空二叉樹只有一個根節點根節點只有左子樹根節點只有右子樹根節點既有左子樹又有右子樹
Q：特殊的二叉樹有哪些
（1）滿二叉樹：在一顆二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。
（2）完全二叉樹：對于一顆具有 n 個結點的二叉樹按層序編號，如果編號為i（1<=i<=n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同，則稱這棵二叉樹為完全二叉樹。滿二叉樹是一種特殊的完全二叉樹。
性質一：在二叉樹的第 i 層上至多有2^(i-1) 個結點。
性質二：深度為 k 的二叉樹至多有2^(k)-1個結點。
性質三：對任何一棵二叉樹, 如果度為0，其葉結點個數為 n0, 度為2的分支結點個數為 n2,則有n0＝n2 + 1。
性質四：具有 n 個結點的完全二叉樹的深度為
性質五：對于具有 n 個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從 0 開始編號，則對于任意結點 i 有：
如果 i=1，則結點 i 是二叉樹的根，無雙親；如果 i>1，則其雙親是結點 1/2如果 2i>n，則結點 i無左孩子；否則其左孩子是結點2i如果 2i<n，則結點 i無右孩子；否則其右孩子是結點2i+1
順序結構存儲就是使用數組來存儲，一般使用數組只適合表示完全二叉樹。因為不是完全二叉樹會有空間的浪費。而現實中使用中只有堆才會使用數組來存儲，二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹。
二叉樹每個結點最多有兩個孩子，所以為它分配一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。結點結構如圖：
代碼演示
typedef int BTDataType;
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當前節點左孩子
struct BinTreeNode* _pRight; // 指向當前節點右孩子
BTDataType _data; // 當前節點值域
}以上就是關于“C++樹與二叉樹實例分析”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
