[Day19]程序菜鸟自学C++资料结构演算法 – 二元搜寻树(Binary Search Tree,BST)

前言：昨天先烧为带大家认识最简单的搜寻类型，今天要来介绍之前有稍微提到的二元搜寻树，并实作给大家看看。

二元搜寻树：

又可称为有序二元树（ordered binary tree）或排序二元树（sorted binary tree），先来讲讲二元搜寻树的定义。
属於二元树的一种，如果任意的节点的左右子树都不为空的话，则左子树节点的值<根节点的值<右子树节点的值，任意节点的左右子树也都为二元搜寻树，但不允许存在关键字相同的两个节点。
通常使用链结串列当作二元搜寻树的储存结构。

如何用二元搜寻树进行查找？其实非常简单，因为右子节点的值一定大於左子节点的值，所以一开始只要从跟节点比较，就可以知道要往左子树还是柚子树前进，再与其他子节点比较，就能找出最後所要找的值。

AVL Tree(Adelson-Velsky and Landis Tree)：

中文称为高度平衡二元搜寻树，任一节点对应的两棵子树的最大高度差为一，所以平常在新增和删除节点的时候都需要对节点作旋转，以保持树的高度是否平衡。
上图就是标准的AVL Tree，现在简单示范如何旋转节点达到平衡。

下图明显是高度(红字)不平衡的二元搜寻树。

所以必须以3为中心点，顺时针旋转来达到树的平衡。

稍微介绍完就来实际建立一遍！
有很多程序与之前写的Tree类似，可以从那边复制过来。

这样就成功显示出要搜寻的值和没有搜寻到的值了。

也可以利用叠代法找出想要的值。
叠代：重复回馈过程的活动，通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次「叠代」，而每一次叠代得到的结果会被用来作为下一次叠代的初始值。

一样可以得到相同的结果。

第一个方法是利用递回的方式一步步找到目标，而第二种方法是利用指针来找到想要的值。

接着来把二元搜寻树写得更完整！
先来实作插入节点。

可以看到新增原本没有的23，不仅排序没有乱掉，而且有搜寻的到，还有新增原本就有的25也不会造成节点的值重复。

也同样可以使用叠代法执行，因为结果都一样，所以就不放上来了。

最後来做节点的删除。

可以看到刚刚加入的23顺利被删除了

本日小结：呼~今天一口气讲完了二元搜寻树，东西非常多要花几天吸收也无访，况且节点的删除比较复杂，因为还得涉及删除後子节点改指向谁，这部分一定要多加小心才不会出错喔！明天会来介绍「杂凑」的搜寻法໒( ͡ᵔ▾ᵔ )७

参考连结：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;
}