数据结构 -二叉搜索树

一.什么是二叉搜索树

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

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

尾递归可以用循环递归

三.二叉树的插入操作

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;
}

原文地址：https://blog.csdn.net/wwwwwgery/article/details/143779890

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！