樹的概念及結(jié)構(gòu)
1.樹的概念及結(jié)構(gòu)
1.1 樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
☆有一個特殊的結(jié)點，稱為根結(jié)點，根節(jié)點沒有前驅(qū)結(jié)點
☆除根節(jié)點外，其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼
☆因此，樹是遞歸定義的。
tips：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)
☆子樹是不相交的
☆除了根節(jié)點外，每個結(jié)點有且僅有一個父節(jié)點
☆一顆N個結(jié)點的樹有N-1條邊
1.2 樹的相關(guān)知識
☆節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度； 如上圖：A的為5
☆葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點； 如上圖：B、G、H、M等節(jié)點為葉節(jié)點
☆非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點； 如上圖：D、E、F等節(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é)點的度稱為樹的度； 如上圖：樹的度為5
☆節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；
☆樹的高度或深度：樹中節(jié)點的最大層次； 如上圖：樹的高度為4
☆堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；如上圖：G、H互為兄弟節(jié)點
☆節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先
☆子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖：所有節(jié)點都是A的子孫
☆森林：由m（m>0）棵互不相交的樹的集合稱為森林
1.3 樹的結(jié)構(gòu)體表示
樹結(jié)構(gòu)相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，既保存值域，也要保存結(jié)點和結(jié)點之間的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。這里展示最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* Child; // 第一個孩子結(jié)點
struct Node* Brother; // 指向其下一個兄弟結(jié)點
DataType data; // 結(jié)點中的數(shù)據(jù)域
};
1.4 樹的實際運用
比如操作系統(tǒng)中的目錄樹結(jié)構(gòu)
2.二叉樹概念及結(jié)構(gòu)
2.1 二叉樹的概念
一棵二叉樹是結(jié)點的一個有限集合，該集合:
☆ 或者為空
☆ 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成
二叉樹
從上圖可以看出：
☆二叉樹不存在度大于2的結(jié)點
☆二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
tips：對于任意的二叉樹都是由以下幾種情況復合而成的：
2.2 現(xiàn)實中的二叉樹
2.3 特殊的二叉樹
☆**滿二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是 ，則它就是滿二叉樹。
該圖來自百度百科
☆完全二叉樹：**完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
該圖來自百度百科
2.4 二叉樹的性質(zhì)
★若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第x層上最多有2^(x-1)個結(jié)點.
★若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h-1.
★對任何一棵二叉樹, 如果度為0其葉結(jié)點個數(shù)為N0, 度為2的分支結(jié)點個數(shù)為N2,則有N0＝N2＋1
★ 若規(guī)定根節(jié)點的層數(shù)為1，具有n個結(jié)點的滿二叉樹的深度h=log2(n+1)(2為底，n+1為對數(shù)）
★對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號，則對于序號為x的結(jié)點有
- 若x>0，i位置節(jié)點的雙親序號：(x-1)/2；x=0，x為根節(jié)點編號，無雙親節(jié)點
- 若2x+1<n，左孩子序號：2x+1，2x+1>=n否則無左孩子
- 若2x+2<n，右孩子序號：2x+2，2x+2>=n否則無右孩子
2.5 二叉樹的存儲結(jié)構(gòu)
二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈式結(jié)構(gòu)。
★順序存儲
順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
★ 鏈式存儲
二叉樹的鏈式存儲結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址 。鏈式結(jié)構(gòu)又分為二叉鏈和三叉鏈，數(shù)據(jù)結(jié)構(gòu)入門學習一般都是二叉鏈，高階數(shù)據(jù)結(jié)構(gòu)會涉及如紅黑樹等會用到三叉鏈。
二叉鏈的結(jié)構(gòu)體表示：
typedef int BTDataType;
struct BinaryTreeNode
{
struct BinTreeNode* Left; // 指向當前節(jié)點左孩子
struct BinTreeNode* Right; // 指向當前節(jié)點右孩子
BTDataType data; // 當前節(jié)點值域
}
三叉鏈的結(jié)構(gòu)體表示：
struct BinaryTreeNode
{
struct BinTreeNode* Parent; // 指向當前節(jié)點的雙親
struct BinTreeNode* Left; // 指向當前節(jié)點左孩子
struct BinTreeNode* Right; // 指向當前節(jié)點右孩子
BTDataType data; // 當前節(jié)點值域
}；
結(jié)語
在下一期的更新中，作者會寫到堆的應(yīng)用和實現(xiàn)，在這篇文章中的理論知識摘錄于網(wǎng)絡(luò)，有興趣的小伙伴可以關(guān)注作者，如果覺得內(nèi)容不錯，請給個一鍵三連吧，蟹蟹你喲?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-412809.html
制作不易，如有不正之處敬請指出
感謝大家的來訪，UU們的觀看是我堅持下去的動力
在時間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-412809.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門（C語言版）二叉樹概念及結(jié)構(gòu)（入門）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
