一.什么是二叉搜索树

树插入删除方便比线性数组

二.二叉搜索树的查找操作

尾递归可以用循环递归

三.二叉树的插入操作

35要挂在33上面必须记住33的位置

解决方法，要求递归函数返回一个 结点插到33的右子树

四.二叉搜索树的删除

要是删除的是叶子节点之间删除

只有一个结点，删除33这个节点，删除之后33的父节点指向子孙结点35

好处左子树的最大值，右子树的最小值一定不是有两个孩子的结点,左子树的最大值一定在最右边，右子树的最小值一定在最左边边

变成了前面的情况要么没儿子要么只要一个

假设要删除的值在左子树

BST->Left=Delete(X,BST->Left),从这个树里删除这个结点变成从左子树里删除这个结点

 左子树删除完之后有可能根节点发生变化

有一种情况删除的是下面的结点跟不变，另一种左子树只有一个结点这个结点就是你要删除的结点，所以左子树便空了返回NULL

BTS=BTS->Left,删除一个结点之后返回新的左子树根节点的地址

Tmp=FindMin(BTS->Right)从右子树里找最小值

然后BTS->Data=Tmp->Data替代这个要被删除的结点

然后BST->Right=Delete(BTS->Data,BTS->Right)再删除这个右子树里的最小值

找到要删除的结点且左右子树有一个不为空，

if(!BTS-<Left)这个结点的左子树为空就

BST=BST->Right把这个结点右子树赋给要删除的结点

 return BST将来再返回这个结点

左右两边都空的情况，左边空了右边进行复制右边是空

#include<iostream>
using namespace std;
#include<queue>
typedef int ElementType;
typedef struct TNode* poist;
typedef poist BinTree;
typedef struct TNode {
	ElementType Data;
	BinTree L;
	BinTree R;
};

BinTree Insert(BinTree BTS,ElementType x) {
	if (!BTS) {
		BTS = new TNode();
		BTS->Data = x;
		BTS->L = BTS->R = NULL;
	}
	else {
		if (x < BTS->Data) {
			BTS->L = Insert(BTS->L, x);
		}
		else if (x > BTS->Data) {
			BTS->R = Insert(BTS->R, x);
		}
	
	}
	return BTS;
}

BinTree Find(BinTree BTS, ElementType x) {
	if (!BTS) return NULL;
	if (x < BTS->Data)
		return Find(BTS->L, x);
	else if (x > BTS->Data)
		return Find(BTS->R, x);
	else
		return BTS;
	
}
BinTree Find(ElementType x, BinTree BTS) {
	while (BTS) {
		if (x < BTS->Data)
			BTS = BTS->L;
		else if (x > BTS->Data)
			BTS = BTS->R;
		else
			return BTS;
	}
	return NULL;
}
void banli(BinTree BTS) {
	if (BTS) {
		cout << BTS->Data << " ";
		banli(BTS->L);
		banli(BTS->R);
	}
}
BinTree FindMax(BinTree BTS) {
	if (BTS) {
		while (BTS->R)BTS = BTS->R;
	}
	return BTS;
}
BinTree FindMin(BinTree BTS) {
	if (!BTS)return NULL;
	else if (!BTS->L)
		return BTS;
	else
		return FindMin(BTS->L);
}
BinTree Delete(ElementType x, BinTree BTS) {
	poist Tmp;
	if (!BTS)cout << "要删除的元素未找到";
	else if (x < BTS->Data)
		BTS->L = Delete(x, BTS->L);
	else if (x > BTS->Data)
		BTS->R = Delete(x, BTS->R);
	else
		if (BTS->L && BTS->R) {
			Tmp = FindMin(BTS->R);
			BTS->Data = Tmp->Data;
			BTS->R = Delete(BTS->Data, BTS->R);
		}
		else {
			Tmp = BTS;
			if (!BTS->L)
				BTS = BTS->R;
			else if (!BTS->R)
				BTS = BTS->L;
			delete Tmp;
		}
	return BTS;
}
int main()
{
	BinTree T2;
	BinTree T1 = new TNode();
	T1->Data = 22;
	Insert(T1, 3);
	Insert(T1, 7);
	Insert(T1, 8);
	Insert(T1, 1);
	Insert(T1, 19);
	Insert(T1, 12);
	Insert(T1, 6);
	T2 = Find(T1,1);
	
	cout <<"查找:" << T2->Data << endl;
	T2 = Find(12, T1);
	cout << "查找:"<<T2->Data << endl;
	T2 = FindMax(T1);
	cout <<"查找最大值:"<< T2->Data << endl;
	T2 = FindMin(T1);
	cout << "查找最小值:" << T2->Data << endl;
	cout << "删除前:";
	banli(T1);
	cout << endl;
	cout << "删除后";
	T1=	Delete(22, T1);
	banli(T1);
	return 0;
}