免責(zé)聲明：

主要從事網(wǎng)頁(yè)設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、響應(yīng)式網(wǎng)站、程序開發(fā)、微網(wǎng)站、小程序定制開發(fā)等，憑借多年來在互聯(lián)網(wǎng)的打拼，我們?cè)诨ヂ?lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了豐富的網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷經(jīng)驗(yàn)，集策劃、開發(fā)、設(shè)計(jì)、營(yíng)銷、管理等多方位專業(yè)化運(yùn)作于一體，具備承接不同規(guī)模與類型的建設(shè)項(xiàng)目的能力。

• 筆記來源：本系列所有筆記均整理自 B站·王道考研·數(shù)據(jù)結(jié)構(gòu) 視頻教程。
• 參考書籍：《2021年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》，王道論壇所著，電子工業(yè)出版社出版，ISBN ：9787121379819。

目錄

1 樹 1.1 樹的概念

樹，由 n （n >= 0）個(gè)結(jié)點(diǎn)組成的有限集。

• 樹中除了根結(jié)點(diǎn)外，其他節(jié)點(diǎn)有且僅有一個(gè)前驅(qū)
• 樹值所有節(jié)點(diǎn)可以有0個(gè)或者多個(gè)后繼
• 樹是一種遞歸的邏輯結(jié)構(gòu)，同時(shí)也是一種分層結(jié)構(gòu)
• 空樹：n 為0時(shí)
• 非空數(shù)：n >0 時(shí)
  • 只有一個(gè)根結(jié)點(diǎn)
  • 其余子結(jié)點(diǎn)又可以作為一棵樹（每棵子樹的結(jié)點(diǎn)集不想交）
• 樹的高度：也叫深度，即樹總的有多少層
• 結(jié)點(diǎn) 的深度：從上往下數(shù)，結(jié)點(diǎn)在第幾層（也叫結(jié)點(diǎn) 的層次）
• 結(jié)點(diǎn)的高度： 從下往上數(shù)，結(jié)點(diǎn)在第幾層
• 結(jié)點(diǎn)的度：某個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)
  • 度大于0：分支結(jié)點(diǎn)、非終端結(jié)點(diǎn)
  • 度等于0：葉子結(jié)點(diǎn)、終端結(jié)點(diǎn)
• 樹的度：各結(jié)點(diǎn)中度的大值
• 邊：連接兩個(gè)結(jié)點(diǎn)的路徑
• 路徑長(zhǎng)度：從起始結(jié)點(diǎn)到達(dá)目標(biāo)結(jié)點(diǎn)需要經(jīng)過幾條邊（只能從上到下）
  
• 有序樹：邏輯上，樹中結(jié)點(diǎn)的各子樹，從左到右是有次序的，不能交換位置
• 無序樹：邏輯上，樹中結(jié)點(diǎn)的各子樹，從左到右是無次序的，可以交換位置

1.2 樹的基本性質(zhì)

• 總結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1
• 度為 m 的樹與m叉樹的區(qū)別

• 高度為h的m叉樹，最多有（m^h - 1）/ (m - 1)個(gè)結(jié)點(diǎn)，最少有h個(gè)結(jié)點(diǎn)
• 高度為 h 度 為m的樹，至少有h + m - 1個(gè)結(jié)點(diǎn)
  

2 二叉樹 2.1 二叉樹的概念

二叉樹是一種每個(gè)結(jié)點(diǎn)最多只有兩棵子樹的樹，子樹分別叫做左子樹和右子樹，其順序不能交換。即便樹中只有一顆子樹，也要區(qū)分是左子樹還是右子樹。因此，二叉樹中不存在度大于2的結(jié)點(diǎn)。

2.2 特殊的二叉樹 滿二叉樹與完全二叉樹

二叉搜索樹

平衡二叉樹

2.3 二叉樹的基本性質(zhì)

性質(zhì)1

性質(zhì)2

性質(zhì)3

完全二叉樹的性質(zhì)

3、二叉樹的存儲(chǔ)結(jié)構(gòu) 3.1 順序存儲(chǔ)

對(duì)于一棵完全二叉樹，采用順序存儲(chǔ)結(jié)構(gòu)如下：


對(duì)于普通的二叉樹，為了讓數(shù)組下標(biāo)能夠反應(yīng)出結(jié)點(diǎn)間的邏輯關(guān)系，只能添加一些并不存在的虛擬結(jié)點(diǎn)，讓其與完全二叉樹相對(duì)應(yīng)起來，如下：

但是這種方式，使得存儲(chǔ)空間利用率降低，而且不方便判斷是某個(gè)結(jié)點(diǎn)是否有左或右孩子，也不方便判斷這個(gè)結(jié)點(diǎn)是否屬于葉子結(jié)點(diǎn)。因此對(duì)于二叉樹，一般使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3.2 鏈?zhǔn)酱鎯?chǔ)

二叉鏈表的結(jié)點(diǎn)，至少包含三個(gè)域：

• 數(shù)據(jù)域
• 左孩子指針域
• 右孩子指針域
  
  

鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)二叉樹定義：

#includenamespace MYTREE{using std::cout;
	using std::endl;

	// 鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)二叉樹
	// 二叉樹結(jié)點(diǎn)定義
	struct TreeNode {int data; // 數(shù)據(jù)域
		TreeNode* lc; // 指向左孩子節(jié)點(diǎn)的指針
		TreeNode* rc; // 指向右孩子節(jié)點(diǎn)的指針
	};
	// 二叉樹
	typedef TreeNode* BinaryTree;

	// 給指定結(jié)點(diǎn)添加孩子結(jié)點(diǎn)
	// 約定flag：true 表示左孩子 false 表示右孩子
	bool InsertNode(TreeNode* node, bool flag, int value) {if (node == NULL) {	return false;
		}
		// 創(chuàng)建新的結(jié)點(diǎn)
		TreeNode* new_node = new TreeNode;
		new_node->data = value;
		new_node->lc = NULL;
		new_node->rc = NULL;
		
		if (flag) {	// 添加左子結(jié)點(diǎn)
			node->lc = new_node;
		}
		else {	// 添加右子結(jié)點(diǎn)
			node->rc = new_node;
		}
		return true;
	}
}

int main() {using namespace MYTREE;

	// 創(chuàng)建一棵空樹
	BinaryTree tree = NULL;
	// 插入根結(jié)點(diǎn) 1
	tree = new TreeNode;
	tree->data = 1;
	tree->lc = NULL;
	tree->rc = NULL;

	// 插入根結(jié)點(diǎn)的左子結(jié)點(diǎn) 2
	InsertNode(tree, true, 2);
	// 插入根結(jié)點(diǎn)的右子結(jié)點(diǎn) 3
	InsertNode(tree, false, 3);
	// 給跟結(jié)點(diǎn)的左孩子結(jié)點(diǎn)插入右子結(jié)點(diǎn) 4
	InsertNode(tree->lc, false, 4);
	// 給跟結(jié)點(diǎn)的右孩子結(jié)點(diǎn)插入左子結(jié)點(diǎn) 6
	InsertNode(tree->rc, true, 6);
	// 給跟結(jié)點(diǎn)的右孩子結(jié)點(diǎn)插入右子結(jié)點(diǎn) 7
	InsertNode(tree->rc, false, 7);
	// 給跟結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的右孩子結(jié)點(diǎn)插入右子結(jié)點(diǎn) 11
	InsertNode(tree->lc->rc, false, 11);
	// 給跟結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn)插入左子結(jié)點(diǎn) 12
	InsertNode(tree->rc->lc, true, 12);
}

使用兩個(gè)指針表示左右孩子結(jié)點(diǎn)，可以很方便的訪問到左右孩子結(jié)點(diǎn)，但是要訪問其父結(jié)點(diǎn)就只能從頭遍歷，可以根據(jù)實(shí)際情況，在結(jié)點(diǎn)中增設(shè)一個(gè)父結(jié)點(diǎn)指針，指向其父結(jié)點(diǎn)，這樣的鏈表稱為三叉鏈表。

4、二叉樹的遍歷 4.1 先序、中序、后續(xù)遍歷

遍歷一棵二叉樹，需要確定對(duì)根結(jié)點(diǎn)N，左子樹L 和右子樹R 的訪問順序，一般按照先左后右的原則，遍歷順序中的序是指訪問根結(jié)點(diǎn)的順序，常見的分為三種：

• 先序遍歷：先訪問跟結(jié)點(diǎn)，再按先序遍歷左子樹，最后按先序遍歷右子樹
• 中序遍歷：先按中序遍歷左子樹，再訪問根結(jié)點(diǎn)，最后按中序遍歷右子樹
• 后序遍歷：先按后序遍歷左子樹，再按后序遍歷右子樹，最后訪問根結(jié)點(diǎn)

對(duì)于有n個(gè)結(jié)點(diǎn)的一棵二叉樹，使用三種遍歷方式的遞歸算法，若不考慮訪問結(jié)點(diǎn)的方式帶來的影響，那么：

• 時(shí)間復(fù)雜度：都是O(n)，因?yàn)槊總€(gè)結(jié)點(diǎn)都只訪問一次
• 空間復(fù)雜度：遞歸工作棧的深度就是樹的深度，假如二叉樹是一顆n個(gè)結(jié)點(diǎn)，深度為n的單支樹，此時(shí)空間復(fù)雜度達(dá)到大O(n)

先序遍歷

// 先序遍歷：根→左孩子→右孩子
void PreOrder(const BinaryTree& tree) {// 如果是空樹，則什么也不做
	if (tree != NULL) {// 最先訪問根結(jié)點(diǎn)
		cout<< tree->data<< " ";
		// 然后訪問左子樹
		PreOrder(tree->lc);
		// 最后訪問右子樹
		PreOrder(tree->rc);
	}
}

中序遍歷

// 中序遍歷
void InOrder(const BinaryTree& tree) {// 如果是空樹，則什么也不做
	if (tree != NULL) {// 最先訪問左子樹
		InOrder(tree->lc);
		// 然后訪問根結(jié)點(diǎn)
		cout<< tree->data<< " ";
		// 最后訪問右子樹
		InOrder(tree->rc);
	}
}

后續(xù)遍歷

// 后序遍歷
void PostOrder(const BinaryTree& tree) {// 如果是空樹，則什么也不做
	if (tree != NULL) {// 最先訪問左子樹
		PostOrder(tree->lc);
		// 然后訪問右子樹
		PostOrder(tree->rc);
		// 最后訪問根結(jié)點(diǎn)
		cout<< tree->data<< " ";
	}
}

4.2 遞歸求二叉樹的深度

// 求二叉樹的深度
int GetDepth(const BinaryTree& tree) {if (tree == NULL) {return 0;
	}
	else {int l = GetDepth(tree->lc); // 求出左子樹的深度
		int r = GetDepth(tree->rc); // 求出由子樹的深度
		// 樹的深度 = Max(左子樹深度，右子樹深度) + 1
		return l >r ? l + 1 : r + 1;
	}
}

4.3 層次遍歷

二叉樹的層序遍歷是指，從上到下，從左到右一次遍歷每個(gè)結(jié)點(diǎn)，需要借助隊(duì)列完成。

• 根結(jié)點(diǎn)入隊(duì)，然后出隊(duì)
• 針對(duì)出隊(duì)結(jié)點(diǎn)，若存在左子樹，則左子樹根結(jié)點(diǎn)入隊(duì)；若存在右子樹，則右子樹根結(jié)點(diǎn)入隊(duì)，然后出隊(duì)
• 再訪問出隊(duì)結(jié)點(diǎn)，循環(huán)第二步，直到隊(duì)列為空

使用一個(gè)鏈?zhǔn)疥?duì)列來存儲(chǔ)二叉樹的結(jié)點(diǎn)指針：

// 鏈?zhǔn)疥?duì)列的一個(gè)節(jié)點(diǎn)
struct LQNode {// 數(shù)據(jù)域存儲(chǔ)的是二叉樹的一個(gè)結(jié)點(diǎn)的指針
	TreeNode* data;
	LQNode* next;
};
// 鏈?zhǔn)疥?duì)列
struct LinkQueue {LQNode* front; // 隊(duì)頭指針，指向第一個(gè)節(jié)點(diǎn)或者指向頭結(jié)點(diǎn)
	LQNode* rare; // 隊(duì)尾指針，指向最后一個(gè)節(jié)點(diǎn)
};

// 帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列 初始化
void InitLinkQueue(LinkQueue& queue) {// 初始時(shí)，隊(duì)頭指針、隊(duì)尾指針都指向頭結(jié)點(diǎn)
	queue.front = queue.rare = new LQNode;
	// 頭結(jié)點(diǎn)的next指針域指向空
	queue.front->next = NULL;
}

// 帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列 判斷是否為空
bool LinkQueueIsEmpty(LinkQueue queue) {// 通過頭指針與尾指針是否指向同一個(gè)位置判斷
	return queue.front == queue.rare;
}

// 帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列 入隊(duì)
// 將 一個(gè)指向二叉樹結(jié)點(diǎn)的指針 TreeNode* 存入隊(duì)列尾部
bool LinkQueueIn(LinkQueue& queue, TreeNode* node_pointer) {// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)
	LQNode* s = new LQNode;
	if (s == NULL) {// 分配內(nèi)存失敗
		return false;
	}
	// 將數(shù)據(jù)存入新的節(jié)點(diǎn)
	s->data = node_pointer;
	// 新節(jié)點(diǎn)應(yīng)該是最后一個(gè)節(jié)點(diǎn)，它的指針域應(yīng)該指向NULL
	s->next = NULL;
	// 將新的節(jié)點(diǎn)插入到隊(duì)尾（只能從隊(duì)尾插入）
	queue.rare->next = s;
	// 隊(duì)尾指針后移,指向新插入的節(jié)點(diǎn)
	queue.rare = s;
	return true;
}

// 帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列 出隊(duì)
// 使用引用變量的方式，將一個(gè)指向二叉樹結(jié)點(diǎn)的指針 TreeNode* 返回 
bool LinkQueueOut(LinkQueue& queue, TreeNode*& node_pointer) {if (queue.front == queue.rare) {return false; // 空隊(duì)列
	}
	// 指向要出隊(duì)的節(jié)點(diǎn)
	// 隊(duì)首結(jié)點(diǎn)是頭結(jié)點(diǎn)的后繼節(jié)點(diǎn)
	LQNode* p = queue.front->next;
	// 先使用引用變量將要出隊(duì)的元素返回
	node_pointer = p->data;
	// 修改頭結(jié)點(diǎn)的后繼節(jié)點(diǎn)
	queue.front->next = p->next;
	// 如果此時(shí)是最后一個(gè)元素出隊(duì)
	if (queue.rare == p) {// 隊(duì)尾指針也指向頭結(jié)點(diǎn)
		queue.rare = queue.front;
	}
	// 釋放內(nèi)存空間
	delete p;
	return true;
}

層序遍歷二叉樹：

// 層序遍歷
void LevelOrder(const BinaryTree& tree) {// 輔助隊(duì)列
	LinkQueue queue;
	// 初始化空隊(duì)列
	InitLinkQueue(queue);
	// 當(dāng)前訪問的結(jié)點(diǎn)
	TreeNode* p = NULL;
	// 根結(jié)點(diǎn)入隊(duì)
	LinkQueueIn(queue, tree);
	// 如果隊(duì)列不為空，開始循環(huán)
	while (!LinkQueueIsEmpty(queue)) {// 隊(duì)頭節(jié)點(diǎn)出隊(duì)
		LinkQueueOut(queue, p);
		// 訪問出隊(duì)結(jié)點(diǎn)數(shù)據(jù)域
		cout<< p->data<< " ";
		// 如果左子樹不為空，左子樹根結(jié)點(diǎn)入隊(duì)
		if (p->lc != NULL) {	LinkQueueIn(queue, p->lc);
		}
		// 如果右子樹不為空，右子樹根結(jié)點(diǎn)入隊(duì)
		if (p->rc != NULL) {	LinkQueueIn(queue, p->rc);
		}

	}
}

4.4 由遍歷序列構(gòu)造二叉樹

若只給出一棵二叉樹的前序遍歷序列或中序遍歷序列或后序遍歷序列或?qū)有虮闅v序列，無法確定唯一的一棵二叉樹。由中序遍歷序列和其他三個(gè)中的任意一個(gè)遍歷序列組合，就能確定唯一的二叉樹：

5 線索二叉樹 5.1 線索二叉樹的概念

傳統(tǒng)的二叉鏈表，僅僅能體現(xiàn)父子關(guān)系，無法表達(dá)出結(jié)點(diǎn)在遍歷序列中的前驅(qū)或后繼。

以普通二叉樹的中序遍歷為例：

• 每次都必須從根結(jié)點(diǎn)出發(fā)
• 無法找到某個(gè)結(jié)點(diǎn)在遍歷序列中的前驅(qū)（基于遍歷序列定義的前驅(qū)）

包含n個(gè)節(jié)點(diǎn)的二叉樹中，存在 n+1 個(gè)空指針域?？梢岳眠@些空指針域，來存放結(jié)點(diǎn)在遍歷序列中的前驅(qū)指針和后繼指針。

因此，根據(jù)如下規(guī)定，若某個(gè)結(jié)點(diǎn)：

• 沒有左子樹，讓左孩子指針 lc 指向其遍歷序列中的前驅(qū)結(jié)點(diǎn)
• 沒有右子樹，讓右孩子指針 rc 指向其遍歷序列中的前驅(qū)結(jié)點(diǎn)
• 增加兩個(gè)標(biāo)識(shí)域，存放標(biāo)識(shí)左右指針?biāo)赶虻氖亲?右孩子還是前驅(qū)/后繼

中序線索二叉樹，以中序序列為依據(jù)進(jìn)行線索化。先序線索二叉樹與后續(xù)線索二叉樹同理。

5.2 二叉樹線索化

#include// 線索二叉樹
namespace CLUE_BINARY_TREE {using std::cout;
	using std::endl;

	typedef int E;

	// 定義線索二叉樹的結(jié)點(diǎn)
	struct CBTreeNode {E data;// 數(shù)據(jù)域
		CBTreeNode* lc; // 左孩子指針或者前驅(qū)結(jié)點(diǎn)指針
		CBTreeNode* rc; // 右孩子指針或者后繼結(jié)點(diǎn)指針
		int l_tag; // 左指針標(biāo)識(shí)，0表示指向的是左孩子，1表示指向的是前驅(qū)
		int r_tag; // 右指針標(biāo)識(shí)，0表示指向的是右孩子，1表示指向的是后繼
	};
	// 線索二叉樹
	typedef CBTreeNode* CBTree;

	// 給指定結(jié)點(diǎn)添加孩子結(jié)點(diǎn) 約定flag：true 表示左 false 表示右
	bool AddNode(CBTreeNode* node, bool flag, E value) {if (node == NULL) {	return false; // 指定結(jié)點(diǎn)不能為空
		}
		CBTreeNode* new_node = new CBTreeNode; // 創(chuàng)建新的結(jié)點(diǎn)
		new_node->data = value;
		new_node->lc = NULL;
		new_node->rc = NULL;
		if (flag) {	node->lc = new_node; // 添加左子結(jié)點(diǎn)
		}
		else {	node->rc = new_node;// 添加右子結(jié)點(diǎn)
		}
		return true;
	}


	// 構(gòu)建一棵二叉樹
	void BuildTree(CBTree& tree) {// 創(chuàng)建 根結(jié)點(diǎn)
		tree = new CBTreeNode;
		tree->data = 1;
		tree->lc = NULL;
		tree->rc = NULL;

		AddNode(tree, true, 2); // 根結(jié)點(diǎn)添加左孩子
		AddNode(tree, false, 3); // 根結(jié)點(diǎn)添加右孩子

		AddNode(tree->lc, true, 4); // 根結(jié)點(diǎn)的左孩子添加左孩子
		AddNode(tree->lc, false, 5); // 根結(jié)點(diǎn)的左孩子添加右孩子

		AddNode(tree->rc, true, 6); // 根結(jié)點(diǎn)的右孩子添加左孩子
		AddNode(tree->rc, false, 7); // 根結(jié)點(diǎn)的右孩子添加右孩子

		AddNode(tree->rc->rc, true, 8); // 根結(jié)點(diǎn)的右孩子 的右孩子 添加左孩子
		AddNode(tree->rc->rc, false, 9); // 根結(jié)點(diǎn)的右孩子 的右孩子 添加右孩子
	}

	void Visit(const CBTree& tree) {cout<< tree->data<< " ";
	}

	// 普通二叉樹的中序遍歷
	void InOrder(const CBTree& tree) {if (tree != NULL) {	// 先訪問左子樹
			InOrder(tree->lc);
			// 訪問根結(jié)點(diǎn)
			Visit(tree);
			// 后訪問右子樹
			InOrder(tree->rc);
		}
	}

	// 通過中序遍歷對(duì)二叉樹進(jìn)行線索化遞歸算法
	// p 指向正在訪問的結(jié)點(diǎn)；pre 指向剛剛訪問過的結(jié)點(diǎn)
	void InClue(CBTree& p, CBTree& pre) {if (NULL != p) {	// 遞歸線索化左子樹
			InClue(p->lc, pre);
			// 左子樹為空，則建立前驅(qū)線索
			if (NULL == p->lc) {		p->lc = pre; // 指向前驅(qū)結(jié)點(diǎn)
				p->l_tag = 1; // 表示lc指向的是前驅(qū)結(jié)點(diǎn)
			}
			// 建立前驅(qū)結(jié)點(diǎn)的后繼線索
			if (NULL != pre && NULL == pre->rc) {		pre->rc = p; // 指向后繼結(jié)點(diǎn)
				pre->r_tag = 1; // 表示rc指向的是后繼結(jié)點(diǎn)
			}
			// 標(biāo)記當(dāng)前結(jié)點(diǎn)為剛剛訪問過的結(jié)點(diǎn)
			pre = p;
			// 遞歸線索化右子樹
			InClue(p->rc, pre);
		}
	}

	// 建立中序線索二叉樹
	void CreateInCBTree(CBTree& tree) {// 指向剛剛訪問過的結(jié)點(diǎn)的指針
		CBTreeNode* pre = NULL;
		// 如果是非空二叉樹，則進(jìn)行線索化
		if (NULL != tree) {	// 線索化二叉樹
			InClue(tree, pre);
			// 處理遍歷序列中的最后一個(gè)節(jié)點(diǎn)
			pre->rc = NULL;
			pre->r_tag = 1;
		}
	}

	// 求中序線索二叉樹 中序序列的第一個(gè)結(jié)點(diǎn)
	CBTreeNode* GetFirst(CBTreeNode* p) {while (p->l_tag == 0) {	p = p->lc;
		}
		return p;
	}
	// 求線索二叉樹中，中序序列的最后結(jié)點(diǎn)
	CBTreeNode* GetLast(CBTreeNode* p) {while (p->r_tag == 0) {	p = p->rc;
		}
		return p;
	}

	// 求線索二叉樹中，結(jié)點(diǎn)p在中序序列下的后繼結(jié)點(diǎn)
	CBTreeNode* GetNext(CBTreeNode* p) {if (p->r_tag == 0) {	return GetFirst(p->rc);
		}
		else {	// 為 1 直接返回后繼線索
			return p->rc;
		}
	}

	// 求線索二叉樹中，結(jié)點(diǎn)p在中序序列下的前驅(qū)結(jié)點(diǎn)
	CBTreeNode* GetPre(CBTreeNode* p) {if (p->l_tag == 0) {	return GetLast(p->lc);
		}
		else {	// 為 1 直接返回前驅(qū)線索
			return p->lc;
		}
	}



	// 中序線索二叉樹的遍歷
	void InClueOrder1(CBTree tree) {for (CBTreeNode* p = GetFirst(tree); p != NULL; p = GetNext(p)) {	Visit(p); // 訪問結(jié)點(diǎn)
		}
	}

	// 中序線索二叉樹的逆向遍歷
	void InClueOrder2(CBTree tree) {for (CBTreeNode* p = GetLast(tree); p != NULL; p = GetPre(p)) {	Visit(p); // 訪問結(jié)點(diǎn)
		}
	}

}

int main() {using namespace CLUE_BINARY_TREE;

	CBTree tree;
	BuildTree(tree);
	// 普通中序遍歷線索二叉樹
	// InOrder(tree);
	cout<< endl;
	// 構(gòu)建中序線索二叉樹
	CreateInCBTree(tree);
	// 遍歷中序線索二叉樹
	InClueOrder1(tree);
	cout<< endl;
	InClueOrder2(tree);
}

6 樹的存儲(chǔ)結(jié)構(gòu)

6.1 雙親表示法

#define MAX_SIZE 100

typedef int E;
// 樹的結(jié)點(diǎn)定義
struct TreeNode {E data; // 數(shù)據(jù)域
	int parent; // 雙親的位置域
};

// 樹的定義
struct MyTree {TreeNode nodes[MAX_SIZE]; // 結(jié)點(diǎn)數(shù)組
	int n; // 結(jié)點(diǎn)數(shù)
};

6.2 孩子表示法

6.3 孩子兄弟表示法

6.4 樹的遍歷 先根遍歷

后根遍歷

層次遍歷

7 樹與二叉樹的應(yīng)用 7.1 二叉排序樹 BST

// 鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)二叉樹
// 二叉樹結(jié)點(diǎn)定義
struct TreeNode {int data; // 數(shù)據(jù)域
	TreeNode* lc; // 指向左孩子節(jié)點(diǎn)的指針
	TreeNode* rc; // 指向右孩子節(jié)點(diǎn)的指針
};
// 二叉樹
typedef TreeNode* BinaryTree;

查找操作

左子樹結(jié)點(diǎn)值< 根結(jié)點(diǎn)值< 右子樹結(jié)點(diǎn)值：

• 若樹非空，目標(biāo)值與根結(jié)點(diǎn)值比較
• 如果相等，則查找成功
• 如果不相等，則繼續(xù)查找
  • 小于根結(jié)點(diǎn)，在左子樹上查找
  • 大于根結(jié)點(diǎn)，在右子樹上查找
• 查找成功返回結(jié)點(diǎn)指針，查找失敗，返回NULL

// 查找，非遞歸實(shí)現(xiàn)，空間復(fù)雜度 O(1)
TreeNode* Search1(BinaryTree tree, int e) {while (tree != NULL && e != tree->data) {// 目標(biāo)值在右子樹上
		if (e >tree->data) {	tree = tree->rc;
		}
		// 目標(biāo)值在左子樹上
		else {	tree = tree->lc;
		}
	}
	return tree;
}
// 查找，遞歸實(shí)現(xiàn)，空間復(fù)雜度O(h)，h表示樹的高度
TreeNode* Search2(BinaryTree tree, int e) {if (tree == NULL) {// 查找失敗
		return NULL;
	}
	if (e == tree->data) {return tree; // 查找成功
	}
	else if (e< tree->data) {// 在左子樹上查找
		return Search2(tree->lc,e);
	}
	else {// 在右子樹上查找
		return Search2(tree->rc,e);
	}
}

插入操作

若原二叉排序樹為空，則直接插入結(jié)點(diǎn)，否則，若關(guān)鍵字 k 小于根結(jié)點(diǎn)的值，將其插入到左子樹上，若關(guān)鍵字 k 大于根結(jié)點(diǎn)的值，將其插入到右子樹上。

// 插入，遞歸實(shí)現(xiàn)，空間復(fù)雜度O(h)，h 為二叉樹的高度
bool Insert1(BinaryTree& tree, int e) {if (tree == NULL) {// 空樹，直接插入到根結(jié)點(diǎn)
		tree = (BinaryTree)malloc(sizeof(TreeNode));
		tree->data = e;
		tree->lc = tree->rc = NULL;
		return true;
	}
	else if (e == tree->data) {// 存在相同關(guān)鍵字結(jié)點(diǎn)，插入失敗
		return false;
	}
	else if (e< tree->data) {// 在左邊插入
		Insert1(tree->lc, e);
	}
	else {// 在右邊插入
		Insert1(tree->rc, e);
	}
}

可以使用插入函數(shù)，構(gòu)造一棵二叉搜索樹：

// 通過一個(gè)數(shù)組構(gòu)造一棵二叉排序樹
void BuildBST(BinaryTree& tree, int arr[], int n) {tree = NULL;
	int i = 0;
	while (i< n) {Insert1(tree, arr[i]);
		i++;
	}
}

刪除操作

先搜索找到目標(biāo)結(jié)點(diǎn)：

• 若即將被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，那么直接刪除即可
• 若即將被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹，那么在刪除該節(jié)點(diǎn)后，將其子樹作為其父結(jié)點(diǎn)的子樹即可
• 若即將被刪除的結(jié)點(diǎn) z 既有左子樹又有右子樹
  • 讓 z 結(jié)點(diǎn)在中序遍歷序列中的直接前驅(qū)（左子樹中大的結(jié)點(diǎn)）或直接后繼（右子樹中最小的結(jié)點(diǎn)）代替 z，然后再刪除這個(gè)直接前驅(qū)（或直接后繼）

查找效率分析

查找成功時(shí)的查找長(zhǎng)度：

最壞的情況：每個(gè)結(jié)點(diǎn)只有一個(gè)分支，樹的高度h等于結(jié)點(diǎn)數(shù)n，平均查找長(zhǎng)度 O(n)
最好的情況：n 個(gè)節(jié)點(diǎn)的二叉樹，達(dá)到最小高度，即 log2n 向下取整再加1，此時(shí)的平均查找長(zhǎng)度為 O(log2n)

查找失敗時(shí)的查找長(zhǎng)度：

7.2 平衡二叉樹

平衡二叉樹（Balanced Binary Tree），簡(jiǎn)稱平衡樹（AVL樹）：樹上任一結(jié)點(diǎn)的左子樹和右子樹的高度差不超過1。

結(jié)點(diǎn)的平衡因子= 左子樹的高度 - 右子樹的高度

因此，平衡二叉樹的各結(jié)點(diǎn)的平衡因子只可能是 -1或0或1。

平衡二叉樹的定義

// 平衡二叉樹的結(jié)點(diǎn)定義
struct AVLNode {int key; // 數(shù)據(jù)域
	int balance; // 平衡因子
	AVLNode* lc; // 左孩子指針
	AVLNode* rc; // 右孩子指針
};
// 平衡二叉樹定義
typedef AVLNode* AVLTree;

平衡二叉樹的調(diào)整

二叉排序樹在插入結(jié)點(diǎn)后，如何保持平衡，使得查找操作的時(shí)間復(fù)雜度達(dá)到最優(yōu)的 O(log2n)？

從新插入結(jié)點(diǎn)往回找到第一個(gè)不平衡的結(jié)點(diǎn)（最小不平衡子樹），調(diào)整以該結(jié)點(diǎn)為根的子樹。

最小不平衡子樹恢復(fù)平衡后，其他受影響的結(jié)點(diǎn)也將恢復(fù)平衡

如何讓最小不平衡子樹恢復(fù)平衡呢？需要分四種情況：

• LL 在A結(jié)點(diǎn)的左孩子的左子樹中插入新的結(jié)點(diǎn)導(dǎo)致不平衡

• RR 在A結(jié)點(diǎn)的右孩子的右子樹中插入新的結(jié)點(diǎn)導(dǎo)致不平衡
  

• LR 在A結(jié)點(diǎn)的左孩子的右子樹中插入新的結(jié)點(diǎn)導(dǎo)致不平衡
  
  

• RL 在A結(jié)點(diǎn)的右孩子的左子樹中插入新的結(jié)點(diǎn)導(dǎo)致不平衡

平衡二叉樹的查找效率

7.3 哈夫曼樹 哈夫曼樹的定義

• 結(jié)點(diǎn)的權(quán)：給樹中的結(jié)點(diǎn)賦予一個(gè)表示某種意義的數(shù)值，這個(gè)數(shù)值就是該結(jié)點(diǎn)的權(quán)。

• 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從根結(jié)點(diǎn)到任意結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)值的乘積，稱為結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。

• 樹的帶權(quán)路徑長(zhǎng)度：所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。

• 哈夫曼樹：在含有 n 個(gè)帶權(quán)葉結(jié)點(diǎn)的二叉樹中，其中帶權(quán)路徑長(zhǎng)度最小的二叉樹叫做最優(yōu)二叉樹，也叫做哈夫曼樹。

如下三個(gè)二叉樹都有 4個(gè)帶權(quán)的葉子結(jié)點(diǎn)：

• 第一個(gè)二叉樹的帶權(quán)路徑長(zhǎng)度：72 + 52 + 22 + 42 = 36
• 第二個(gè)二叉樹的帶權(quán)路徑長(zhǎng)度：73 + 53 + 21 + 42 = 46
• 第三個(gè)二叉樹的帶權(quán)路徑長(zhǎng)度：71 + 52 + 23 + 43 = 35

第三個(gè)二叉樹的帶權(quán)路徑長(zhǎng)度最小，第三個(gè)二叉樹是哈夫曼樹。

哈夫曼樹構(gòu)造

第二種構(gòu)造結(jié)果：

哈夫曼編碼

比如，要傳遞四個(gè)字符 A B C D

• 固定長(zhǎng)度編碼
  • 每個(gè)字符使用相等長(zhǎng)度的二進(jìn)制位表示，比如 ASCII 編碼，使用8個(gè)bit位二進(jìn)制表示一個(gè)字符:
    • A : 0100 0001
    • B : 0100 0010
    • C : 0100 0011
    • D : 0100 0100
  • 要發(fā)送的字符只有4中形態(tài)，因此可以使用長(zhǎng)度為 2 的二進(jìn)制位表示一個(gè)字符：
    • A : 00
    • B : 01
    • C : 10
    • D : 11
• 可變長(zhǎng)度編碼：對(duì)不同的字符使用不同長(zhǎng)度的二進(jìn)制位表示

前綴編碼：如果不存在一個(gè)編碼是另一個(gè)編碼的前綴，則稱這樣的編碼是前綴編碼，非前綴編碼在解碼是有歧義。

由哈夫曼樹得到哈夫曼編碼：字符集中的每個(gè)字符作為一個(gè)葉子結(jié)點(diǎn)，各個(gè)字符出現(xiàn)的頻度作為結(jié)點(diǎn)的權(quán)值，構(gòu)造出哈夫曼樹（可以將樹的左指針看作二進(jìn)制的0，右指針看作二進(jìn)制的1）。

哈夫曼編碼可以用于數(shù)據(jù)的壓縮。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：第五章樹與二叉樹-創(chuàng)新互聯(lián)
本文URL：http://weahome.cn/article/dpoedd.html