資料結構樹、二叉樹、完全二叉樹、二叉查找樹、平衡二叉樹、紅黑樹、B+樹

樹、二叉樹、平衡二叉樹、二叉搜尋樹

樹的前序周遊、中序周遊和後序周遊

樹的前序周遊、中序周遊和後續周遊是以周遊時根所在的位置順序命名的。層次周遊即按層從上至下，從左至右周遊即可。

• 前序周遊：根->左子樹->右子樹
• 中序周遊：左子樹->根->右子樹
• 後序周遊：左子樹->右子樹->根

以下圖為例，前序周遊的結果則是：ABDGHCEIF；中序周遊的結果是GDHBEICF；後序周遊的結果是GHDBIEFCA。

二叉樹

二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”和“右子樹”。二叉樹具有以下性質：

• 性質1：二叉樹第i層上的結點數目最多為 2 i − 1 2^{i-1} 2i−1 (i≥1)。
• 性質2：深度為k的二叉樹至多有 2 k − 1 2^{k}-1 2k−1個結點 (k≥1)。
• 性質3：包含n個結點的二叉樹的高度至少為 l o g 2 ( n + 1 ) log_2^ {(n+1)} log2(n+1)​。

• 性質4：在任意一棵二叉樹中，若終端結點的個數為 n 0 n_0 n0​，度為2的結點數為 n 2 n_2 n2​，則 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。

  性質4的證明：設總節點數位n，則n= n 0 + n 1 + n 2 n_0+n_1+n_2 n0​+n1​+n2​;除了根節點以外，隻有葉子節點和非葉子節點并且所有節點都隻有一個分支進入，是以 n − 1 = n 1 + 2 n 2 n-1=n_1+2n_2 n−1=n1​+2n2​(由度建立的等式）,聯力則可得到 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。

采用遞歸、非遞歸分别實作前序周遊、中序周遊和後續周遊

仍然以上面的樹為列，通過前序輸入建立二叉樹，輸入依次為：ABDG##H###CE#I##F##

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
	char val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char x) :val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	//以前序方式建立二叉樹
	void createBiTree(TreeNode* &T) {  //注意：&的意思是傳進來節點指針的引用，目的是讓傳遞進來的指針發生改變
		char c;
		std::cout<<"輸入節點value，#表示為空\n";
		std::cin >> c;
		if (c == '#') {  //當遇到#時，令樹的根節點為NULL，進而結束該分支的遞歸
			T = NULL;
		}
		else {
			T = new TreeNode(c);
			createBiTree(T->left);
			createBiTree(T->right);
		}
	}
	/*方法一：采用遞歸實作周遊*/

	//遞歸前序（根左右）
	void printPreTree(TreeNode* T) {
		if (T != NULL) {
			std::cout << T->val;
			printPreTree(T->left);
			printPreTree(T->right);
		}
	}
	//遞歸中序（左根右）
	void printMidTree(TreeNode* T) {
		if (T != NULL) {
			printMidTree(T->left);
			std::cout << T->val;
			printMidTree(T->right);
		}
	}
	//遞歸後序（左右根）
	void printPostTree(TreeNode* T) {
		if (T != NULL) {
			printPostTree(T->left);
			printPostTree(T->right);
			std::cout << T->val;
		}
	}

	/*方法一：采用非遞歸實作周遊*/
	//非遞歸前序（根左右）
	//
	void printPreTreeNoRecursion(TreeNode* T) {
		stack<TreeNode*> mystack;
		TreeNode* pre = NULL;
		while (!mystack.empty() || T != NULL) {
			while (T != NULL) {  //把左孩子壓入棧内
				std::cout << T->val;
				mystack.push(T);
				T = T->left;
			}
			//當T為空時，說明根和左子樹都周遊完了，該進入右子樹了
			if (!mystack.empty()) {//出棧+壓右孩子入棧
				T = mystack.top();
				mystack.pop();
				T = T->right;
			}
		}
	}
	//非遞歸中序（左根右）
	void printMidTreeNoRecursion(TreeNode* T) {
		stack<TreeNode*> mystack;
		TreeNode* pre = NULL;
		while (!mystack.empty() || T != NULL) {
			while (T != NULL) {  //把左孩子壓入棧内
				mystack.push(T);
				T = T->left;
			}
			//當T為空時，說明根和左子樹都周遊完了，該進入右子樹了
			if (!mystack.empty()) {//出棧+壓右孩子入棧
				T = mystack.top();
				std::cout << T->val;
				mystack.pop();
				T = T->right;
			}
		}

	}
	//遞歸後序（左右根）
	void printPostTreeNoRecursion(TreeNode* T) {
		stack<TreeNode*> mystack;
		TreeNode* pre = NULL;
		TreeNode* pLastVisit=NULL;//記錄上一次通路的點
		while (T != NULL) {  //走到最左下端
			mystack.push(T);
			T = T->left;
		}
		while (!mystack.empty()) {
			T = mystack.top();
			mystack.pop();
			//根節點被通路：右子樹為空||右子樹已經被通路
			if (T->right == NULL || T->right == pLastVisit)
			{
				std::cout << T->val;
				pLastVisit = T;//修改上次通路節點
			}
			else {
				mystack.push(T); //根節點再次入棧
				T = T->right;   //此時右子樹一定沒被通路
				while (T != NULL) {
					mystack.push(T);
					T = T->left;
				}
			}
		}
	}
};

int main()
{
	Solution s;
	TreeNode* T=NULL;
	s.createBiTree(T);
	std::cout << "二叉樹建立完成\n";
	//前序列印
	std::cout << "遞歸前序列印的結果為：";
	s.printPreTree(T);
	std::cout << "\n";
	std::cout << "遞歸中序列印的結果為：";
	s.printMidTree(T);
	std::cout << "\n";
	std::cout << "遞歸後序列印的結果為：";
	s.printPostTree(T);
	std::cout << "\n";
	std::cout << "非遞歸前序列印的結果為：";
	s.printPreTreeNoRecursion(T);
	std::cout << "\n";
	std::cout << "非遞歸中序列印的結果為：";
	s.printMidTreeNoRecursion(T);
	std::cout << "\n";
	std::cout << "非遞歸後序列印的結果為：";
	s.printPostTreeNoRecursion(T);
	return 0;
}

           

完全二叉樹

1. 完全二叉樹是一種特殊的二叉樹，滿足以下要求：

   （1）所有葉子節點都出現在 k 或者 k-1 層，而且從 1 到 k-1 層必須達到最大節點數；

   （2）第 k 層可以不是滿的，但是第 k 層的所有節點必須集中在最左邊。

   （3）任何一個節點不能隻有左子樹沒有右子樹

   （4）葉子節點隻出現在最後一層或者倒數第二層

2. 完全二叉樹的應用：堆排序
3. 當我們用數組實作一個完全二叉樹時，n個節點按層編号（從0開始），然後知道一個節點的位置，就可以輕松地算出它的父節點、孩子節點的位置。比如編号為i的節點：

• 其父節點的編号為 ( i − 1 ) 2 \frac{(i-1)}{2} 2(i−1)​;
• 如果 2 ∗ i + 1 &lt; n 2*i+1&lt;n 2∗i+1<n，其左子樹的根節點編号為 2 ∗ i + 1 2*i+1 2∗i+1，否則沒有左子樹
• 如果 2 ∗ i + 2 &lt; n 2*i+2&lt;n 2∗i+2<n，其右子樹的根節點編号為 2 ∗ i + 2 2*i+2 2∗i+2，否則沒有右子樹

二叉查找樹

1. 二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

   （1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

   （2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

   （3）左、右子樹也分别為二叉排序樹；

   （4）沒有鍵值相等的節點。

2. 最壞情況下，比如當先後插入的關鍵字有序時，生成的二叉排序樹退化為單枝樹，其實就是一個連結清單，時間複雜度為 O ( n ) O(n) O(n)，最好的情況是如果二叉排序樹是平衡的，則n個節點的二叉排序樹的高度為 L o g 2 ( n + 1 ) Log_2^{(n+1)} Log2(n+1)​,其查找效率為 O ( L o g 2 n ) O(Log_2^{n}) O(Log2n​)，其通路性能近似于折半查找。

平衡二叉樹（AVL樹）

可以參考清華大學資料結構C++第七章，從zig/zag旋轉的角度講解的非常明白

1. 平衡二叉樹又被稱為AVL樹，或者一顆空樹，或者是具備以下特征的一種特殊的二叉查找樹：

   （1）它的左右兩個子樹的高度差(平衡因子)的絕對值不超過1；

   （2）并且左右兩個子樹都是一棵平衡二叉樹；

2. 平衡因子：左子樹的高度-右子樹的高度

   以下圖為例，左邊每個節點的平衡因子絕對值均不超過1，為平衡二叉樹；右邊樹中存在平衡因子絕對值超過2的節點，不是平衡二叉樹

   

3. 平衡二叉樹的目的是為了減少二叉查找樹層次，提高查找速度；平衡二叉樹可以解決二叉查找樹退化成連結清單的問題，把插入，查找，删除的時間複雜度最好情況和最壞情況都維持在 O ( l o g N ) O(logN) O(logN)。

4. 平衡調節： 當我們往一個平衡二叉樹插入一個新的子節點，可能造成平衡二叉樹的失衡，即存在有節點的平衡因子為2或者-2的狀态，是以我們需要調節二叉樹，使之保持平衡。通常會出現四種情況，是以需要四種操作來平衡二叉樹。【注意：旋轉過程中要注意平衡二叉樹是二叉排序樹的特點】

   (1)右旋：當有節點的平衡因子為2時，說明左邊子樹深度大于右邊，是以需要右旋。

   

   (2)左旋：當有節點的平衡因子為-2時，說明右邊的子樹的深度大于左邊，是以需要左旋。

   

   (3)右左旋：先讓子樹4和6右旋，再整體左旋

   

   (4)左右旋：先讓子樹2和4左旋，再整體右旋

   

5. 僞代碼【ZIG/ZAG】

   

紅黑樹R-B Tree

1. 紅黑樹，是一種平衡二叉樹。紅黑樹的每個節點上都有存儲位表示節點的顔色，可以是紅或黑。滿足：

   （1）每個節點或者是黑色，或者是紅色。

   （2）根節點是黑色。

   （3）每個葉子節點是黑色。【注：這裡葉子節點，是指為空(NIL或NULL)的葉子節點】

   （4）如果一個節點是紅色的，則它的子節點必須是黑色的。

   （5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

   【注】：特性(3)中的葉子節點，是隻為空(NIL或null)的節點；特性(5)確定沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對接近平衡的二叉樹。

   

2. 紅黑樹的應用比較廣泛，主要是用它來存儲有序的資料，它的時間複雜度是O(logN)，效率非常之高

B+樹

B樹：有序數組+平衡多叉樹；

B+樹：有序數組連結清單+平衡多叉樹；

B+樹的關鍵字全部存放在葉子節點中，非葉子節點用來做索引，而葉子節點中有一個指針指向一下個葉子節點。

B+樹隻要周遊葉子節點就可以實作整棵樹的周遊

參考資料

二叉樹前序周遊、中序周遊、後序周遊、層序周遊的直覺了解

二叉樹，平衡二叉樹，紅黑樹，B-樹、B+樹、B*樹的差別

大話資料結構之平衡二叉樹

一步步分析為什麼B+樹适合作為索引的結構