二叉樹
- 1. 樹的概念及結構
- 1.1樹的概念
- 1.2 樹的表示
- 2. 二叉樹的概念及結構
- 2.1 概念
- 2.2 資料結構中的二叉樹
- 2.3 特殊的二叉樹
- 2.4 二叉樹的存盤結構
- 2.4.1 順序存盤
- 2.4.2 練習（增強對于二叉樹的結點認識）
1. 樹的概念及結構
1.1樹的概念
樹是一種非線性的資料結構，它是由n個有限結點組成一個具有層次關系的集合，把它叫做樹是因為他看起來像一顆倒掛的樹，也就是說他是根朝上，而葉朝下的，任何一顆樹都可以看做是根結點和子樹的概念，
有時候我們會把根節點處稱為深度0，那么當是空樹的時候，根結點就是-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）棵互不相交的樹的集合稱為森林；
1.2 樹的表示
樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法，孩子表示法、孩子兄弟表示法等等，我們這里就簡單的了解其中最常用的孩子兄弟表示法（也叫左孩子右兄弟表示法），
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個孩子結點
struct Node* _pNextBrother; // 指向其下一個兄弟結點
DataType _data; // 結點中的資料域
};
2. 二叉樹的概念及結構
2.1 概念
一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成，
二叉樹的特點：
- 每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點，
- 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，
2.2 資料結構中的二叉樹
2.3 特殊的二叉樹
- 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數（高度）為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹，
- 完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，（簡單點說就是：對于K-1層的結點都是滿的，最后一層可以不滿，但是必須滿足添加時從左到右連續）
2.4 二叉樹的存盤結構
二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構，
二叉樹的性質
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i-1) 個結點.
- 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h- 1.
- 對任何一棵二叉樹, 如果度為0其葉結點個數為 n0, 度為2的分支結點個數為 n2,則有n0＝n2＋1
- 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度h=Log2(n+1). (ps：Log2(n+1)是log以2為底，n+1為對數)
- 對于具有n個結點的完全二叉樹5，如果按照從上至下從左至右的陣列順序對所有節點從0開始編號，則對于序號為i的結點有：
① 若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點（i表示child結點下標，來求雙親結點的下標）
②若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
③ 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子
（但是對于完全二叉樹來說，如果沒有左孩子，那么一定不會存在右孩子）
2.4.1 順序存盤
順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，關于堆我們后面的章節會專門講解，二叉樹順序存盤在
物理上是一個陣列，在邏輯上是一顆二叉樹，
2.4.2 練習（增強對于二叉樹的結點認識）
1 . 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（A）
A 不存在這樣的二叉樹
B 200
C 198
D 199
答案：葉子結點的個數是度為2的結點個數+1
2.下列資料結構中，不適合采用順序存盤結構的是（A）
A 非完全二叉樹
B 堆
C 佇列
D 堆疊
答案：參考2.4.1
3.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（A）
A n
B n+1
C n-1
D n/2
答案：假設葉子結點是x，那么度為2的結點是x-1，x+x-1 +1 = 2n（因為這里的結點數是偶數個，所以這里肯定有度為1的結點，不然他不可能是偶數個）
4.一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（B）
A 11
B 10
C 8
D 12
答案：一個滿二叉樹的結點個數是2^ h - 1 那么 2^h- 1 = 531 你會發現最接近的是h=9 但是2 ^ 9 才是512 都不滿足 531個結點，所以h=10，是一個完全二叉樹，最后一層不滿，只有19個結點，
5.一個具有767個節點的完全二叉樹，其葉子節點個數為（B）
A 383
B 384
C 385
D 386
答案：對于完全二叉樹來說除了度為2的或者度為0的，剩下的就是度為1的，假設度為2的為x-1，那么葉子結點就是x，那么x+x-1 = 767 得x = 384
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248092.html
標籤：其他
下一篇：PS基礎知識大雜燴