數據結構學習筆記＜4＞二叉樹

一、什麼是樹#

1. 樹的定義#

樹（Tree）：n（n≥0）個結點構成的有限集合。
當 n=0 時，稱為空樹；
對於任一棵非空樹（n>0），它具備以下性質：

樹中有一個稱為 “根（Root）” 的特殊結點，用 r 表示。
其餘結點可分為 m（m>0）個互不相交的有限集 T1，T2，……，Tm，其中每個集合本身又是一棵樹，稱為原來樹的 “子樹（SubTree）”。
子樹是不相交的
除了根結點外，每個結點有且僅有一個父結點；
一個N 個結點的樹有N-1 條邊。

2. 樹的一些基本術語#

1. 結點的度（Degree）：結點擁有子結點的數量
2. 樹的度： 最大的結點的度稱為樹的度
3. 葉結點（Leaf）： 度為 0 的結點
4. 父結點（Parent）： 如果有上一个結點，則稱這個上一結點是它的父結點，如果沒有上一結點，則這個屬性則無父結點。
5. 子結點（Child）：若 A 結點是 B 結點的父結點，則稱 B 結點是 A 結點的子結點；子結點也稱孩子結點
6. 兄弟結點（Sibling）：具有同一父結點的各結點彼此是兄弟結點。
7. 路徑和路徑長度：從結點 n1 到 nk 的路徑為一個節點序列 n1，n2，……，nk，ni 是 ni+1 的父結點。路徑所包含邊的個數為路徑的長度
8. 祖先結點（Ancestor）：沿樹根到某一結點路徑上的所有節點都是這個結點的祖先結點
9. 子孫結點（Descendant）：某一結點的子樹中所有結點是這個結點的子孫
10. 結點的層次（Level）：規定根結點在 1 層，其它任一結點的層數是其父結點的層數加 1。
11. 樹的深度（Depth）：樹中所有結點的最大層次是這棵樹的深度。
12. 森林： m 棵不相交的樹的集合

二、樹的表示#

1. 兒子 - 兄弟表示法#

在這裡插入圖片描述

三、二叉樹#

1. 定義#

二叉樹 T: 一個有窮的結點集合。
這個結點可以為空
若不為空，則它是由根結點和稱為其左子樹 TL和右子樹 TR的兩個不相交的二叉樹組成
二叉樹具體五種基本形態 a 空樹 b 只有一個結點 c 有一個結點和左子樹 d 有一個結點和左子樹 e 有一個結點和左右子樹
在這裡插入圖片描述
PS：二叉樹的子樹有左右順序之分

幾種特殊二叉樹
在這裡插入圖片描述
二叉樹的抽象數據類型定義
類型名稱：二叉樹
數據對象集：一個有窮的結點集合。
若不為空，則由根結點和其左、右二叉子樹組成。
操作集：BT∈BinTree，Item∈ElementType，重要操作有：

Boolean IsEmpty (BinTree BT); // 判別 BT 是否為空
void Traversal (BinTree BT); // 遍歷，按某順序訪問某個結點；
BinTree CreatBinTree (); // 創建一個二叉樹

常用的遍歷方法有：

void PreOrderTraversal(BinTree BT); //先序--- 根、左子樹、右子樹
void InOrderTraversal(BinTree BT); //中序--- 左子樹、根、右子樹
void PostOrderTraversal(BinTree BT); //後序--- 左子樹、右子樹、根
void LevelOrderTraversal(BinTree BT); //層次遍歷，從上到下、從左到右

2. 二叉樹的幾個重要性質#

一個二叉樹第 i 層的最大節點數為 2^i-1^，i≥1。
深度為 k的二叉樹有最大結點總數為 2^k^-1，k≥1。
對任何非空二叉樹 T，若 n0 表示葉結點的個數、n2 是度為 2 的非葉結點個數，那麼兩者滿足關係 n0=n2+1。
具有n 個結點的完全二叉樹的深度 k必為log~2~n+1

3. 二叉樹的存儲結構#

1、順序存儲結構#

完全二叉樹：按從上至下、從左到右順序存儲n個結點的完全二叉樹的結點父子關係

非根結點（序號 i > 1）的父結點的序號是 [i / 2] ;(向下取整)
結點（序號為 i）的左孩子的序號是 2i(2i ≤ n，否則沒有左孩子)
結點（序號為 i）的右孩子的序號是 2i+1(2i + 1 ≤ n，否則沒有右孩子)

一般二叉樹也可採用這種順序存儲結構，但是會造成空間浪費

滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點的二叉樹，區別於完全二叉樹在這裡插入圖片描述

2、鏈式存儲#

(1) 定義#

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
		ElementType Data;
		BinTree Left;
		BinTree Right;
}

(2) 遍歷（遞歸實現）#

先序遍歷：

1. 先訪問根結點；
2. 先序遍歷其左子樹；
3. 先序遍歷其右子樹。

void PreOrderTraversal(BinTree BT) {
	if(BT) {
		printf("%d", BT->Data);
		PreOrderTraversal( BT->Left);
		PreOrderTraversal( BT->Right);
	}
}

中序遍歷：

1. 中序遍歷其左子樹
2. 訪問根結點
3. 中序遍歷其右子樹。

void InOrderTraversal(BinTree BT) {
	if(BT) {
		InOrderTraversal( BT->Left);
		printf("%d", BT->Data);
		InOrderTraversal( BT->Right);
	}
}

後序遍歷：

1. 後序遍歷其左子樹
2. 後序遍歷其右子樹。
3. 訪問根結點

void PostOrderTraversal(BinTree BT) {
	if(BT) {
		PostOrderTraversal( BT->Left);
		PostOrderTraversal( BT->Right);
		printf("%d", BT->Data);
	}
}

(2) 遍歷（非遞歸實現）#

基本思路：使用堆棧或隊列

中序遍歷非遞歸遍歷算法

遇到一個結點，就把它壓棧，並去遍歷它的左子樹；
當左子樹遍歷結束後，從棧頂彈出這個結點並訪問它；
然後按其右指針再去中序遍歷該結點的右子樹。

void InOrderTraversal(BinTree BT) {
	BinTree T = BT;
	Stack S = CreatStack(MaxSize);//創建並初始化堆棧S
	while( T || !IsEmpty(S) ) {
		while(T) {//一直向左並將沿途結點壓入堆棧
			Push(S, T);
			T = T->Left;
		}
		if( !IsEmpty(S) ) {
			T = Pop(S);	//結點彈出堆棧
			printf("%5d", T->Data);//訪問結點
			T = T->Right;//轉向右子樹
		}
	}
}

層序遍歷

需要一個存儲結構保存暫時不訪問的結點（堆棧、隊列）
隊列實現：遍歷從根節點開始，首先將根節點入隊，然後開始執行循環：結點出隊、訪問該節點、其左右兒子入隊
1. 根結點入隊；
2. 從隊列中取出一個元素；
3.訪問該元素所指結點；
4. 若該元素所指結點的左、右孩子結點非空，將其左、右孩子的指針順序入隊。

void LevelOrderTraversal(BinTree BT) {
	Queue Q;  BinTreee T;
	if ( !BT ) return;	//若是空樹直接返回
	Q = CreateQueue(MaxSize);//創建並初始化隊列Q
	AddQ(Q, BT);
	while( !IsEmpty(Q) ) {
		T = DeleteQ(Q);
		printf("%d\n", T->Data);//訪問結點
		if(T->Left) AddQ(Q, T->Left);//將左孩子放入隊列
		if(T->Right) AddQ(Q, T->Right);//將右孩子放入隊列
	}
}

補充知識
數據管理的基本操作之查找：根據某個給定關鍵字 K，從集合 R 中找出關鍵字與 K 相同的記錄，分為靜態查找與動態查找
靜態查找：集合中記錄是固定的，沒有插入和刪除操作，只有查找。
法 1：順序查找（哨兵概念：在數組的邊界上設一個值，碰到哨兵循環就可以結束了，可以少一個分支判斷）複雜度 O (n);
法 2：二分查找（前提：數組連續且有序）
動態查找：集合中記錄時動態變化的，除查找外還可能發生插入和刪除