数据结构：第7章：查找(复习）

顺序查找：

ASL=

折半查找：

这里 j 表示 二叉查找树的第 j 层

二叉排序树：

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，定义：

1. 对于二叉排序树的每个节点，其左子树的所有节点的值都小于该节点的值。
2. 对于二叉排序树的每个节点，其右子树的所有节点的值都大于该节点的值。
3. 对于二叉排序树的每个节点，其左右子树也分别是二叉排序树。

可以发现二叉排序树的定义时递归定义。

这些性质保证了对于二叉排序树中的任意节点，其左子树的节点值小于它，右子树的节点值大于它，从而形成了一种有序的结构。

二叉排序树的有序性质使得在其中进行查找、插入和删除等操作时具有较高的效率。对于给定的值，可以通过比较节点的值，按照二叉排序树的性质在树中快速定位所需的节点。

二叉排序树的难点在于删除树中的某个值。删除某个键值为 key 的节点时，有三中情况要考虑：

1.该节点 r 的左孩子为空：r=r->lch;

2.该节点 r 的右孩子为空：l=l->rch;

3.该节点的左右孩子均不位空：选择左孩子中 key 值最大的节点替换 r；

4.?(程序题)

二叉排序树插入、删除

键盘输入若干整型数据，以0做结束，利用二叉排序树的插入算法创建二叉排序树，并中序遍历该二叉树。之后输入一个整数x，在二叉排序树中查找，若找到则输出“该数存在”，否则输出“该数不存在”；再输入一个要删除的一定存在的整数y，完成在该二叉树中删除y的操作，并输出删除y后的二叉树中序遍历的结果。

输出数据之间用一个空格分隔。

输入：
1 5 4 2 3 6 8 7 9 11 14 13 12 16 19 0
输出：
1 2 3 4 5 6 7 8 9 11 12 13 14 16 19
输入：
19
输出：
该数存在
输入：
14
输出：
1 2 3 4 5 6 7 8 9 11 12 13 16 19

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;

typedef struct Info {
	int key;
}Info;

typedef struct Node {
	Info data;
	struct Node* lch;
	struct Node* rch;
}Node,*Tree;

void print(Tree& r) {
	if (r == NULL)return;
	print(r->lch);
	cout << r->data.key << " ";
	print(r->rch);
}

void Insert(Tree& r, int key) {
	if (r == NULL) {
		Node* p = new Node;
		p->data.key = key;
		p->rch = p->lch = NULL;
		r = p;
	}
	else if(r->data.key<key) {
		Insert(r->rch, key);
	}
	else {
		Insert(r->lch, key);
	}
}

void build(Tree& r) {
	int in;
	cin >> in;
	while (in) {
		Insert(r, in);
		cin >> in;
	}
}

int search(Tree& r, int key) {
	if (r == NULL)return 0;
	if (r->data.key == key) {
		return 1;
	}
	if (r->data.key < key) {
		if (search(r->rch, key))return 1;
	}
	else {
		if (search(r->lch, key))return 1;
	}
	return 0;
}

int del(Tree& r, int key) {
	if (r == NULL)return 0;
	if (r->data.key == key) {
		if (r->lch == NULL) {
			r =r->rch;
		}
		else if (r->rch == NULL) {
			r =r->lch;
		}
		else {
			//cout << r->data.key << endl;
			Node* p = r->lch;
			Node* fa = r;
			
			while (p->rch != NULL) {
				fa = p;
				p = p->rch;
			}
			Node* t = r;
			if (fa != r)
				fa->rch = p->lch;
			if (r->lch != p)
				p->lch = r->lch;
			p->rch = r->rch;
			//cout << p->data.key << endl;
			r = p;
			delete t;
		}
		return 1;
	}
	if (r->data.key < key) {
		if (del(r->rch, key))return 1;
	}
	else {
		if (del(r->lch, key))return 1;
	}
	return 0;
}

int main() {
	Node* root = NULL;
	build(root);
	print(root);
	int in;
	cin >> in;
	if (search(root, in)) {
		cout << "该数存在" << endl;
	}
	else {
		cout << "该数不存在" << endl;
	}
	cin >> in;
	del(root, in);
	print(root);
	return 0;
}

用例1：

输入

1 5 4 2 3 6 8 7 9 11 14 13 12 16 19 0 19 14

输出

1 2 3 4 5 6 7 8 9 11 12 13 14 16 19 该数存在 1 2 3 4 5 6 7 8 9 11 12 13 16 19

用例2：

输入

10 9 8 7 11 12 13 14 0 14 8

输出

7 8 9 10 11 12 13 14 该数存在 7 9 10 11 12 13 14

用例3：

输入

23 45 67 21 12 15 9 10 55 0 19 9

输出

9 10 12 15 21 23 45 55 67 该数不存在 10 12 15 21 23 45 55 67