目錄

1.樹的概念及結構

1.1樹的概念

1.2樹的相關概念

1.3樹的表示?

?1.4樹在實際中的應用

2.二叉樹概念及結構?

2.1二叉樹的概念

2.2特殊的二叉樹?

2.3二叉樹的性質?

2.4應用題?

---

1.樹的概念及結構

1.1樹的概念

樹是一種非線性的數據結構，由?n（n≥0）個有限節點構成，這些節點按照層次關系組織成一個集合。之所以將其命名為“樹”，是因為它的形態恰似一棵倒置的樹——根在上，枝葉在下

樹是由根節點和子樹構成的，因此樹是遞歸定義的?

樹形結構中，子樹之間不能有交集，否則就不是樹形結構?

1.2樹的相關概念

節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：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.3樹的表示?

在表示樹時，一個節點的度一般是不確定的，所以存儲起來就比較麻煩

既要保存值域，也要保存結點和結點之間的關系，常用的表示方式是：孩子兄弟表示法

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

?A沒有兄弟節點，?_pNextBrother指向空，然后只需要讓_firstChild1指向B節點

B節點中的_pNextBrother就可以指向C，如此往復

想要增加B的兄弟節點，就在C后面尾插，想要增加B的子節點，就在E后面尾插

這種左孩子右兄弟的表示方法有效解決了未知度的問題 ，可以表示任意形狀和度的樹結構

?1.4樹在實際中的應用

在Windows操作系統中，D盤類似于樹結構中的根節點。

D盤中的文件夾形成層次結構，每個文件夾可以包含其他文件夾和文件，類似于樹結構中的子樹

文件在樹結構中通常被視為葉節點，因為它們不包含其他子節點

2.二叉樹概念及結構?

2.1二叉樹的概念

一棵二叉樹是結點的一個有限集合，該集合:

1. 或者為空 2. 由一個根節點加上兩棵分別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出

1. 二叉樹不存在度大于2的結點

2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹?

?注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

2.2特殊的二叉樹?

1. 滿二叉樹：一棵層數（高度）≥1的二叉樹，

其中所有非葉子節點都有兩個子節點，且所有葉子節點位于同一層

2.完全二叉樹：一棵高度為?K?的二叉樹，其前?K?1?層均為滿二叉樹結構，且第?K?層的所有節點均從左至右連續排列，無間隔缺失

所以，滿二叉樹是特殊的完全二叉樹

2.3二叉樹的性質?

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i - 1) 個結點.

2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h - 1

3. 對任何一棵非空二叉樹, 如果度為0的葉結點個數為N0 , 度為2的分支結點個數為N2，

則? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?N0=N2+1

4.一棵K層的完全二叉樹的節點個數范圍 [ 2^(k-1) , 2^k -1 ]

5.完全二叉樹中，?度數為1的節點個數?N1??只能是 0 或 1

4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h= ,則有h = log?(n + 1).

(ps：log?(n + 1)?是log以2 為底，n+1為對數)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2^h - 1 = n? ? ? ? ??h = log?(n + 1)

5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編號，則對 于序號為i的結點有?

1. 若i>0，i位置節點的雙親序號：(i-1)/2；(計算機自動向下取整)

i=0，i為根節點編號，無雙親節點

2. 若2i+1 < n， 左孩子序號：2i+1?若 2i+1 >= n 否則無左孩子

3. 若2i+2 < n， 右孩子序號：2i+2 若 2i+2 >= n 否則無右孩子

如圖所示，

?節點下標的2倍+1為該節點的左孩子的下標，

節點下標的2倍+2為該節點的左孩子的下標

子節點下標-1除以2(計算機自動向下取整)，得到子節點的父親節點的下標

2.4應用題?

1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為()

A 不存在這樣的二叉樹

B 200

C 198

D 199

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?運用公式 N0=N2+1

3.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）

A n

B n+1

C n-1

D n/2

? ? ? ? ? ? ? ?N0=N2+1? ? ? ?2n=N0+N2+N1? ? ? ? ?完全二叉樹中N1= 1或0

4.一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（ ）

A 11

B 10

C 8

D 12

? ? 2^9 = 512? ? ? ? ? 2^10 = 1024

5.一個具有767個節點的完全二叉樹，其葉子節點個數為（）

A 383

B 384

C 385

D 386

?N0=N2+1? ? ? ?767=N0+N2+N1? ? ? ? ?完全二叉樹中N1= 1或0