二叉樹

文章目錄

二叉樹
- 一、樹
- - 1.樹的定義
  - 2. 樹的概念
  - - (1) 節點的度
    - (2) 葉節點(終端節點)
    - (3) 分支節點(非終端節點)
    - (4) 父節點(雙親節點)
    - (5) 子節點(孩子節點)
    - (6) 兄弟節點
    - (7) 樹的度
    - (8) 節點的層次
    - (9) 樹的高度(深度)
    - (10) 堂兄弟節點
- 二、二叉樹
- - 1. 樹的表示
  - 2. 二叉樹
  - 3. 二叉樹的種類
  - - (1) 滿二叉樹
    - (2) 完全二叉樹
  - 4. 二叉樹的性質

二叉樹

在了解二叉樹之前，專業外的人，比如我，二叉樹的名稱早就聽說過，在了解二叉樹之前，應當先去了解樹的幾個概念，畢竟，二叉樹是普通樹中特殊的存在

一、樹

1.樹的定義

樹是一種 非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，

在這里插入圖片描述

B 和 C 是 A 的子節點
有一個特殊的結點(A)，稱為根結點，根節點沒有前驅結點
子樹之間不能有交集，否則就不是樹形結構

在這里插入圖片描述

2. 樹的概念

樹的概念還是很多專有名詞的，還是得多看幾遍才能記住

(1) 節點的度

一個節點含有的子樹的個數稱為該節點的度

在這里插入圖片描述

(2) 葉節點(終端節點)

度為0的節點稱為葉節點

在這里插入圖片描述

(3) 分支節點(非終端節點)

不為0的節點

在這里插入圖片描述

(4) 父節點(雙親節點)

若一個節點含有子節點，則這個節點稱為其子節點的父節點

A 是 B 和 C 的 父節點

(5) 子節點(孩子節點)

一個節點含有的子樹的根節點稱為該節點的子節點

B 和 C 是 A 的 子節點

(6) 兄弟節點

具有相同父節點的節點互稱為兄弟節點

B 和 C 互為 兄弟節點

(7) 樹的度

最大的節點的度稱為樹的度

在這里插入圖片描述

這個數最大的度為2，所以樹的度也為2

(8) 節點的層次

從根開始定義起，根為第1層，根的子節點為第2層，依次遞增

(9) 樹的高度(深度)

樹中節點的最大層次

比如例子中樹的高度為4

(10) 堂兄弟節點

雙親在同一層的節點互為堂兄弟

比如例子中的G 和 H

二、二叉樹

如果要寫一個二叉樹的話，先了解一下樹是怎么寫的

1. 樹的表示

既要保存值域，也要保存結點和結點之間的關系

樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等

我們這里就簡單的了解其中最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{
 struct Node* Child;//第一個孩子結點
 struct Node* Brother;//指向其下一個兄弟結點
 DataType data; //結點中的資料域
};

圖解：

在這里插入圖片描述

2. 二叉樹

度最大為2的樹
有左右之分，左邊為左孩子，右邊為右孩子

在這里插入圖片描述

3. 二叉樹的種類

(1) 滿二叉樹

每個節點的度都是2，則這個二叉樹就是滿二叉樹，

如果一個二叉樹的層數為K，且結點總數是2^k - 1，則它就是滿二叉樹

在這里插入圖片描述

用等比數列求和公式，得出所有的節點加起來是2^k - 1

(2) 完全二叉樹

簡單來說二叉樹中元素是連續的，

如圖：

在這里插入圖片描述

錯誤圖示：

在這里插入圖片描述

4. 二叉樹的性質

二叉樹的 i 行最多有 2^h-1個節點
深度為h的二叉樹，節點數最多有 2^h -1
對任何一棵二叉樹, 如果度為0其葉結點個數為 n0 , 度為2的分支結點個數為 n1
證明: 除了根節點A其他每個節點都有一個從上往下的箭頭

單獨挑出來，放大了看，這是每有一個度為1的節點，有一個箭頭向下：

每有一個度為2的節點就有兩個箭頭，向下

先設
- 一共有n個節點
- 度為0的節點有n0個
- 度為1的節點有n1個
- 度為2的節點有n2個
節點數的兩個式子：

n = n1 + n2 + n0

而 度為0 的沒有這個箭頭，我們拿這個箭頭去算

箭頭個數的式子

n - 1 = n1 + 2n2

兩個式子聯立

得出 n2 = n0 + 1
若規定根節點的層數為1，具有n個結點的滿二叉樹的深度為log2(n + 1)
父親序號為i，找左右孩子

因為每層節點的個數成指數型增長

2⁰、2¹、2²……

可以看出左孩子序號是父親序號的2倍 + 1

可以看出右孩子序號是父親序號的2倍 + 2
孩子序號為i，找父親，反之就行，父親為 (i - 1)/2