UC知道实验四 二叉排序树查找
来源：百度知道 编辑：UC知道 时间：2024/06/06 13:50:47
掌握二叉排序树查找的基本操作。
[具体问题描述]：
写出二叉排序树的查找、插入、建立、删除和打印算法。
[算法提示]：
1、二叉排序树的查找算法。
① 若查找树为空，查找失败。
② 查找树非空，将给定值key与查找树的根结点关键码比较。
③ 若相等，查找成功，结束查找过程，否则，
a．当给key小于根结点关键码，查找将在以左子女为根的子树上继续进行，转①
b．当给key大于根结点关键码，查找将在以右子女为根的子树上继续进行，转①
2、二叉排序树的插入算法。
设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。
3、二叉排序树删除操作。
在二叉排序树中删除一个结点就相当于删除一个有序序列中的某一条记录，当某个记录被删除后仍然要保持序列的有序性。因此当把二叉排序树中某一个结点删除后，不能把以该结点为根的整棵子树都删除，应当保证整棵二叉排序树结构的完整性，保持二叉排序树原有的特点。
假设用P指向二叉排序树上被删除的结点，指针f指向p所指向的结点的双亲结点，删除的关键是如何找一个S结点来替换P结点（即P所指向的结点）的，要分成如下三种情况分别进行处理：
1） 要删除的结点P为叶子结点。
2） 要删除的结点P只有左子树或右子树。
3） 要删除的结点P既有左子树又有右子树。。
4、 二叉排序树的打印算法。
二叉排序树的打印可以利用二叉树的特点，对整个二叉排序树进行中序遍历，所得到的结果为一个按关键字大小进行非递减排列的序列。
#include<iostream.>
using namespace std;
typedef int KeyType;
typedef struct tree//声明树的结构
{
struct tree *left; //存放左子树的指针
struct tree *right; //存放又子树的指针
KeyType key; //存放节点的内容
} BSTNode, * BSTree; //声明二叉树的链表
BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点
{ //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回
BSTree f,p=tptr; //p的初值指向根结点
while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲
{
if(p->key==key) //树中已有key，无须插入
return tptr;
f=p; //f保存当前查找的结点，即f是p的双亲
p=(key<p->key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode)); //生成新结点
p->key=key; p->left=p->right=NULL;
if(tptr==NULL) //原树为空，新插入的结点为新的根
tptr=p;
else
if(key<f->key)
f->left=p;
else
f->right=p;
return tptr;
}
BSTree createBST()//建立二叉树
{
BSTree t=N