二叉樹的基本操作

二叉樹的建立
- 建構二叉樹的類對象
- 建立二叉樹
先序周遊
- 遞歸
- 非遞歸
中序周遊
- 遞歸
- 非遞歸
後序周遊
- 遞歸
- 非遞歸
層序周遊
求解二叉樹的高度
- 最大高度
- 最小高度

二叉樹的建立

建構二叉樹的類對象

在建立一棵二叉樹之前，我們先建立一個二叉樹的類對象Tree。類中包含的成員變量有：val、left、right，函數接口包括：先序周遊、中序周遊、後序周遊、層序周遊、二叉樹高度

typedef int TreeElemt;

class Tree{
public:
	enum Mode{NUM, CHAR};
	
private:
	TreeElemt val;
	Tree *left;
	Tree *right;

	Mode mode;

public:
	Tree();	// 預設構造函數
	Tree(TreeElemt ch);		// 構造一個val為ch的結點

	~Tree();


	// 前中後層序周遊
	void PreOrder();
	void InOrder();
	void PostOrder();
	// 前中後層序周遊——非遞歸
	friend void PreOrder_(const Tree* t);
	friend void InOrder_(Tree* t);
	friend void PostOrder_(Tree* t);
	// 層序周遊
	friend void LevelOrder_(Tree* t);
	// 二叉樹的最大高度
	int maxHeight();
	// 二叉樹的最小高度:根節點到葉子結點（注意是到葉子節點）
	int minHeight();
	
	// 初始化二叉樹
	friend Tree* InitialTree(const std::vector<TreeElemt>& t, int i);

};

由于有些函數用成員函數不好操作，是以我将函數設定為友元

下面我們将逐漸實作上面類中的接口函數。

建立二叉樹

// 建立二叉樹
Tree* InitialTree(const std::vector<TreeElemt>& t, int i){
	Tree* root = new Tree(t[i]);			// 建構根節點
	if (2 * i + 1 < t.size()) root->left = InitialTree(t, 2 * i + 1);	// 建構左子樹
	if (2 * i + 2 < t.size()) root->right = InitialTree(t, 2 * i + 2);	// 建構右子樹
	return root;
}

先序周遊

先序周遊的順序：中左右

如下圖所示：

資料結構：二叉樹的建構、前中後序周遊（遞歸vs非遞歸）思路及代碼二叉樹的建立先序周遊中序周遊後序周遊層序周遊求解二叉樹的高度
使用先序周遊的結果為：1,2,4,8,9,5,3,6,7

遞歸

使用遞歸的方法非常好了解：

先通路根節點；

然後遞歸地通路左子樹；

再遞歸的通路右子樹。

代碼：

// 先序周遊
void Tree::PreOrder(){
	if (this) {
		cout << this->val << " ";			// 通路根節點；
		this->left->PreOrder();				// 遞歸地通路左子樹；
		this->right->PreOrder();			// 遞歸的通路右子樹。
	}
}

非遞歸

使用非遞歸需要用到棧來存儲節點

将根節點先壓入棧中

取出棧頂結點

由于棧的性質是“先進後出”，是以先将右子樹壓入棧中，然後再将左子樹壓入棧中，這樣在處理時就是先處理左子樹，再處理右子樹了。

代碼：

// 前
void PreOrder_(const Tree* t){
	/// 使用非遞歸求解需要用到棧
	/// 思路：将根節點入棧，當彈出一個結點的時候就将它的兩個子節點入棧，
	///      由于要先輸出左子樹，而棧是先進後出，是以應該先壓入右子樹

	stack<const Tree*> s;
	// 将根節點壓入棧中
	s.push(t);
	while (!s.empty()) {
		const Tree* root = s.top();
		cout << s.top()->val << " ";
		s.pop();
		if (root->right) s.push(root->right);	// 右子樹存在，右子樹入棧
		if (root->left) s.push(root->left);		// 左子樹存在，左子樹入棧
	}
}

中序周遊

中序周遊的順序：左中右

那麼上面的圖使用中序周遊的結果為：8，4，9，2，5，1，6，3，7

遞歸

使用遞歸的方法相比于先序周遊隻是換了一下處理節點的位置：

然後遞歸地通路左子樹；

先通路根節點；

再遞歸的通路右子樹。

代碼：

// 中序周遊
void Tree::InOrder(){
	if (this) {
		this->left->InOrder();
		cout << this->val << " ";
		this->right->InOrder();
	}
}

非遞歸

由于中序周遊最先通路的是最左邊的節點，是以我們需要将左結點全部壓入棧中，然後彈出棧頂結點，判斷棧頂結點有沒有右子樹，如果有的話就轉而處理右子樹，沒有的話就繼續彈出棧中的元素。

使用非遞歸進行中序周遊的步驟：

将左子樹全部壓入棧中

彈出棧頂元素，判斷該棧頂元素是否有右子樹，如果有則處理右子樹，即将右子樹中的左右左節點壓入棧中；如果沒有右子樹就繼續處理棧頂結點。如此循環，

代碼:

// 中
void InOrder_(Tree * t) {
	/// 思路：先将所有的左節點入棧，然後彈出一個結點，判斷它有沒有右節點，有則入棧
	if (t == NULL) return;
	stack<Tree*> s;
	s.push(t);
	t = t->left;
	while (!s.empty() || t) {
		// 将所有左子樹入棧
		while (t) {
			s.push(t);
			t = t->left;
		}
		bool flag = true;			// 通過一個flag來控制目前處理的是否為棧頂元素，如果是為true，不是為false

		while (!s.empty() && flag) {
			Tree* p = s.top();
			cout << p->val << " ";
			s.pop();
			if (p->right) {
				t = p->right;
				flag = false;
			}
		}
		
	}
}

後序周遊

後序周遊的順序：左右中

那麼上面的圖使用中序周遊的結果為：8，9，4，5，2，6，7，3，1

遞歸

同先序周遊，遞歸步驟：

然後遞歸地通路左子樹；

再遞歸的通路右子樹；

先通路根節點。

代碼：

// 後序周遊
void Tree::PostOrder(){
	if (this) {
		this->left->PostOrder();
		this->right->PostOrder();
		cout << this->val << " ";
	}
}

非遞歸

後序周遊的非遞歸相對麻煩一點，需要設定兩個控制量，一個用來儲存上一次通路過的結點，一個用來控制目前通路的結點是否為棧頂結點，這個與中序周遊中的flag作用相同。

那麼我們為什麼要設定一個用來儲存上次是否通路過的結點？**因為後序周遊中，我們必須先彈出右結點之後才能彈出根結點，那麼在處理棧頂結點的時候我們先要判斷該棧頂結點是否有右結點，如果有的話就要轉去處理右節點，此時作為根結點的棧頂結點依舊在棧中，而處理完右結點後，這個根結點就不是棧頂結點了，那麼這個根結點之後還有成為棧頂結點的一天，而當我們第二次通路它的時候肯定是它的右結點已經被彈出之後，那麼它的上一次通路的結點肯定就是它的右子樹。于是，我們需要将這個根節點彈出。

後序周遊的順序：

将所有的左子樹壓入棧中；

擷取棧頂結點，判斷棧頂結點的右子樹是否等于上次通路的結點，如果等于則彈出該結點；否則就轉而處理它的右節點。再循環1、2

代碼：

// 後
void PostOrder_(Tree * t){
	/// 思路：将所有的左子樹壓入棧中，擷取棧頂元素（先不彈出），判斷其右子樹是不是剛剛通路過的結點
	///      如果是，那麼就把這個結點彈出來，如果不是，那麼久轉而處理它的右子樹。将它的右子樹壓入棧中。

	if (t == NULL) return;
	Tree *r;			// 儲存上一個通路過的結點，對于還未有通路的時候它未null
	stack<Tree*> s;		
	bool flag;			// 用來判斷目前處理的結點是棧頂結點還是右節點
	s.push(t);
	t = t->left;
	while (!s.empty()){
		while (t){
			s.push(t);
			t = t->left;
		}
		r = NULL;
		flag = true;
		while (!s.empty() && flag) {
			t = s.top();		// 擷取棧頂元素
			// 如果棧頂元素 == 剛剛通路過的元素，那麼就彈出棧頂元素
			if (t->right == r) {
				cout << t->val << " ";
				s.pop();
				r = t;		// r就指向本次通路的結點，對于下次通路的結點而言，它是剛通路過的結點
			}
			// 如果棧頂元素 != 剛通路過的元素，那麼就處理棧頂元素的右節點
			else{
				t = t->right;
				flag = false;		// 此時開始處理右節點，關閉處理棧頂結點的視窗
			}
		}
	}
}

層序周遊

層序周遊用的資料結構是隊列，利用隊列的“先進先出”性質

将根結點壓入隊列中

彈出隊列中的第一個結點，并将該結點的左子樹壓入隊列，再将結點的右子樹壓入隊列。循環2

代碼：

// 層
void LevelOrder_(Tree * t){
	/// 思路：使用隊列，将根節點放入隊列中，取出根節點，放入左子樹，放入右子樹
	if(t==NULL) return;
	queue<Tree*> q;
	q.push(t);
	
	while (!q.empty()){
		t = q.front();
		cout << t->val << " ";
		q.pop();
		if (t->left) q.push(t->left);
		if (t->right) q.push(t->right);
	}
}

求解二叉樹的高度

遞歸求解二叉樹的高度

遞歸終止條件：root == NULL

最大高度

代碼：

// 樹的最大高度
int Tree::maxHeight(){
	if(this == NULL) return 0;
	return max(left->maxHeight(), right->maxHeight()) + 1;
}

最小高度

這裡求的最小高度是從根節點到葉子節點的最小高度（來源leetcode），是以需要對root->left為空或者root->right為空的情況特别考慮。

如果沒有強調說是到達葉子節點的最小高度那麼就直接将最大高度中的max改為min

int Tree::minHeight(){
	if (this == NULL) return 0;
	int h = INT_MAX;
	if (this->right == NULL) return this->left->minHeight() + 1;
	if (this->left == NULL) return this->right->minHeight() + 1;
	return min(this->left->minHeight(), this->right->minHeight()) + 1;
}

資料結構：二叉樹的建構、前中後序周遊（遞歸vs非遞歸）思路及代碼二叉樹的建立先序周遊中序周遊後序周遊層序周遊求解二叉樹的高度

二叉樹的基本操作

二叉樹的建立

建構二叉樹的類對象

建立二叉樹

先序周遊

遞歸

非遞歸

中序周遊

遞歸

非遞歸

後序周遊

遞歸

非遞歸

層序周遊

求解二叉樹的高度

最大高度

最小高度

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希