数据结构 -二叉搜索树

一.什么是二叉搜索树

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

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

尾递归可以用循环递归

三.二叉树的插入操作

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);elsereturn BTS;}
BinTree Find(ElementType x, BinTree BTS) {while (BTS) {if (x < BTS->Data)BTS = BTS->L;else if (x > BTS->Data)BTS = BTS->R;elsereturn 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;elsereturn 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);elseif (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;
}