iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 19

[Day19]程式菜鳥自學C++資料結構演算法 – 二元搜尋樹(Binary Search Tree,BST)

前言:昨天先燒為帶大家認識最簡單的搜尋類型,今天要來介紹之前有稍微提到的二元搜尋樹,並實作給大家看看。

二元搜尋樹:

又可稱為有序二元樹(ordered binary tree)或排序二元樹(sorted binary tree),先來講講二元搜尋樹的定義。
屬於二元樹的一種,如果任意的節點的左右子樹都不為空的話,則左子樹節點的值<根節點的值<右子樹節點的值,任意節點的左右子樹也都為二元搜尋樹,但不允許存在關鍵字相同的兩個節點
通常使用鏈結串列當作二元搜尋樹的儲存結構。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187PdPL4fVOAT.png
如何用二元搜尋樹進行查找?其實非常簡單,因為右子節點的值一定大於左子節點的值,所以一開始只要從跟節點比較,就可以知道要往左子樹還是柚子樹前進,再與其他子節點比較,就能找出最後所要找的值。

AVL Tree(Adelson-Velsky and Landis Tree):

中文稱為高度平衡二元搜尋樹,任一節點對應的兩棵子樹的最大高度差為一,所以平常在新增和刪除節點的時候都需要對節點作旋轉,以保持樹的高度是否平衡。
上圖就是標準的AVL Tree,現在簡單示範如何旋轉節點達到平衡。

下圖明顯是高度(紅字)不平衡的二元搜尋樹。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187eN1OYSNWwo.png
所以必須以3為中心點,順時針旋轉來達到樹的平衡。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187eegvcBeaBg.png

稍微介紹完就來實際建立一遍!
有很多程式與之前寫的Tree類似,可以從那邊複製過來。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187tXB0Tuwx9c.png
https://ithelp.ithome.com.tw/upload/images/20211003/20140187rxTWimrFa5.png

這樣就成功顯示出要搜尋的值和沒有搜尋到的值了。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187764JRGFXIp.png

也可以利用疊代法找出想要的值。
疊代:重複回饋過程的活動,通常是為了接近並到達所需的目標或結果。每一次對過程的重複被稱為一次「疊代」,而每一次疊代得到的結果會被用來作為下一次疊代的初始值。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187J5UiDi0CvD.png
https://ithelp.ithome.com.tw/upload/images/20211003/20140187m3P5UayZ5P.png

一樣可以得到相同的結果。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187hgJpQ39RSy.png
第一個方法是利用遞迴的方式一步步找到目標,而第二種方法是利用指針來找到想要的值。

接著來把二元搜尋樹寫得更完整!
先來實作插入節點。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187vuGf1DLvY2.png

可以看到新增原本沒有的23,不僅排序沒有亂掉,而且有搜尋的到,還有新增原本就有的25也不會造成節點的值重複。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187dwfSOiont9.png
也同樣可以使用疊代法執行,因為結果都一樣,所以就不放上來了。
https://ithelp.ithome.com.tw/upload/images/20211003/201401877iphm8pCpx.png

最後來做節點的刪除。
https://ithelp.ithome.com.tw/upload/images/20211003/20140187FwCzKJI1m1.png
https://ithelp.ithome.com.tw/upload/images/20211003/20140187Nh43r59wkv.png

可以看到剛剛加入的23順利被刪除了
https://ithelp.ithome.com.tw/upload/images/20211003/20140187Z7ToZEUStX.png

本日小結:呼~今天一口氣講完了二元搜尋樹,東西非常多要花幾天吸收也無訪,況且節點的刪除比較複雜,因為還得涉及刪除後子節點改指向誰,這部分一定要多加小心才不會出錯喔!明天會來介紹「雜湊」的搜尋法໒( ͡ᵔ▾ᵔ )७

參考連結:https://zh.wikipedia.org/zh-tw/%E8%BF%AD%E4%BB%A3#:~:text=%E7%96%8A%E4%BB%A3%E6%98%AF%E9%87%8D%E8%A4%87%E5%9B%9E%E9%A5%8B,%E7%96%8A%E4%BB%A3%E7%9A%84%E5%88%9D%E5%A7%8B%E5%80%BC%E3%80%82

#include<iostream>
using namespace std;
using T = int;
struct BiNode {
	T data;
	BiNode* Lchild{ 0 };
	BiNode* Rchild{ 0 };
	BiNode() = default;
	BiNode(T x) : data(x), Lchild(0), Rchild(0) {}
};
BiNode* SearchBST(BiNode* root, T key) { //編寫搜尋函式
	if (!root) return 0; //遞迴出口
	if (root->data == key)return root; //處理跟部
	if (key < root->data) //如果關鍵字在左子樹
		return SearchBST(root->Lchild, key);
	else //如果關鍵字在右子樹
		return SearchBST(root->Rchild, key);
}

BiNode* SearchBST_(BiNode*root,T key) { //利用疊代法找出想要的值
	BiNode* P = root;

	while (P && P->data != key)  //當P不是空的且P的值與關鍵字不同
		if (key < P->data) 
			P = P->Lchild; //將P改為P的左子節點
		else
			P = P->Rchild; //將P改為P的右子節點
		if (!P) return 0;
		return P;
	
}

void Inorder(BiNode* T) {
	if (!T)return;
	Inorder(T->Lchild);
	std::cout << T->data << " ";
	Inorder(T->Rchild);
}

void Preorder(BiNode* T) {
	if (!T) return;
	std::cout << T->data << " ";
	Preorder(T->Lchild);
	Preorder(T->Rchild);
}

void Postorder(BiNode* T) {
	if (!T)return;
	Postorder(T->Lchild);
	Postorder(T->Rchild);
	std::cout << T->data << " ";
}
#include<queue>
void Level_order(BiNode* T) {
	queue<BiNode*> Q;
	Q.push(T);
	while (!Q.empty()) {
		BiNode* p = Q.front();
		Q.pop();
		std::cout << p->data;
		if (p->Lchild) Q.push(p->Lchild);
		if (p->Rchild) Q.push(p->Rchild);
	}
}
BiNode* InsertBST(BiNode* root, T e) {
	if (root == 0) { //如果樹跟沒有值,則直接將值傳回樹跟
		return new BiNode(e);
	}
	if (e < root->data) //左子樹
		root->Lchild = InsertBST(root->Lchild, e);
	else if (e > root->data) //右子樹
		root->Rchild = InsertBST(root->Rchild, e);
	return root;
}
BiNode* InsertBST_(BiNode* root, T e) {
	BiNode* p = root, * parent = 0;
	while (p && p->data != e) {
		parent = p;
		if (e < p->data) p = p->Lchild; //左子樹
		else p = p->Rchild; //右子樹
	}
	if (p) return 0;
	if (!parent) return new BiNode(e);
	else if (e < parent->data) {
		parent->Lchild = new BiNode(e); return parent->Lchild;
	}
	else { parent->Rchild = new BiNode(e); return parent->Rchild; }
}
BiNode* DeleteBST(BiNode* root, T e) { //e為要刪除的值
	if (!root) return root; //如果是空樹則直接返回
	if (e < root->data) //如果e小於根節點的值
		root->Lchild = DeleteBST(root->Lchild, e); //則執行此過程直到值一樣
	else if (e > root->data) //同理
		root->Rchild = DeleteBST(root->Rchild, e);
	else { //相等後開始刪除節點
		if (!root->Lchild && !root->Rchild) { //若沒有左右子樹則直接刪除
			delete(root); return nullptr; //返回空指針
		}
		else if (!root->Rchild) { //若要刪除的節點沒有右子節點
			BiNode* ret = root->Lchild; //則保存左子節點
			delete(root); return ret;
		}
		else if (!root->Lchild) { //概念同上
			BiNode* ret = root->Rchild;
			delete(root); return ret;
		}
		else { //若要刪除的節點有兩個子節點
			BiNode* tmp = root->Rchild; //宣告tmp為root(不一定是根節點)的右子節點
			while (tmp->Lchild) //然後將tmp往左子節點移動直到沒有節點
				tmp = tmp->Lchild;

			root->data = tmp->data; //將tmp和要刪除的節點對調,並更改節點的指針
			root->Rchild = DeleteBST(root->Rchild, e);
		}
	}
	return root;
}
		
int main() {
	BiNode* T = new BiNode(30);
	T->Lchild = new BiNode(20);
	T->Rchild = new BiNode(40);
	BiNode* P = T->Lchild;
	P->Lchild = new BiNode(17); 
	P->Rchild = new BiNode(25);
	BiNode* S = T->Rchild;
	S->Lchild = new BiNode(38); 
	S->Rchild = new BiNode(45); 
	/*
	Inorder(T); std::cout << "\n";
	Preorder(T); std::cout << "\n";
	Postorder(T); std::cout << "\n";
	Level_order(T); std::cout << "\n";

	if (P = SearchBST_(T, 17))
		std::cout << "搜尋的值是:" << P->data << std::endl;
	else
		std::cout << "搜尋失敗,沒有找到:" << 17 << std::endl;
	if (P = SearchBST_(T, 23))
		std::cout << "搜尋的值是:" << P->data << std::endl;
	else
		std::cout << "搜尋失敗,沒有找到:" << 23 << std::endl;
	return 0;*/

	InsertBST(T, 23);
	InsertBST(T, 25);
	Inorder(T); std::cout << "\n";
	Preorder(T); std::cout << "\n";
	Postorder(T); std::cout << "\n";
	if (P = SearchBST_(T, 23))
		std::cout << "搜尋的值是:" << P->data << std::endl;
	else
		std::cout << "搜尋失敗,沒有找到:" << 23 << std::endl;

	std::cout << "刪除:" << 23 << endl;
	T = DeleteBST(T, 23);
	Inorder(T); std::cout << "\n";
	Preorder(T); std::cout << "\n";
	Postorder(T); std::cout << "\n";
	return 0;
}

上一篇
[Day18]程式菜鳥自學C++資料結構演算法 – 線性搜尋法(Linear Search)與二分搜尋法(Half-Interval Search)
下一篇
[Day20]程式菜鳥自學C++資料結構演算法 – 雜湊法(Hash)
系列文
程式菜鳥自學C++資料結構演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言