二叉排序数的实现

二叉排序数的实现

一.论述题

1. 编写SearchBST(T, key)与InsertBST(T, key)的伪代码，并实现；

(1).伪代码：

SearchBST(T, key)
{
	if(T为空 || T->data.key==key)
		return T;
	if(k<T->data.key)
		return 在左子树中查找；
	else
		return 在右子树中查找；
}

代码实现：

BSTree SearchBST(BSTree T, KeyType key){
    if((!T) || key == T->data.key)  
		return T;
    else if(key < T->data.key) 
		return SearchBST(T->lchild, key);
    else 
		return SearchBST(T->rchild, key);
}

(2)伪代码：

InsertBST(T, key)
{
	if(T为空)
	{
		T=new BSTNode;
		T->key=key;
		T->lchild=T->rchild=NULL;
	   return 1;
	}
	else if(存在相同关键字的节点)
	   return 0；
	else if(k<T->key)
	   return 插入到左子树中；
       else 
    	   return 插入到右子树中；
}

2.编写CreateBST(T)的伪代码实现从控制台输入创建BST树。最后使用代码实现。使用“50 30 80 20 40 90 10 25 35 85 23 88”创建BST，并中序输出该BST

CreateBST(T)的伪代码:

CreateBST(T)
{
    T = NULL；
    cin<<关键字；
    while(关键字!=0)
    {
        InsertBST(T,关键字）；//将关键字插入到T所指向的二叉排序树中
        cin<<关键字；
    }   
}

代码实现:

void CreatBST(BSTree &T){
    T = NULL;
    cin >> key;
    while(key != 0){
        InsertBST(T, key);
        cin >> key;
    }
}

创建BST

typedef struct{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct BSTNode{
    ElemType data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
 
ElemType e;
BSTree S, T;
BSTree SearchBST(BSTree T, KeyType key){
    if((!T) || key == T->data.key)  
		return T;
    else if(key < T->data.key) 
		return SearchBST(T->lchild, key);
    else 
		return SearchBST(T->rchild, key);
}
void InsertBST(BSTree &T, ElemType e){
    if(!T){
        S = new BSTNode;
        S->data = e;
        S->lchild = S->rchild = NULL;
        T = S;
    }
    else if(e.key < T->data.key)
        InsertBST(T->lchild,e);
    else if(e.key > T->data.key)
        InsertBST(T->rchild,e);
}
void InOrderTraverse(BSTree T){
 if(T){
  InOrderTraverse(T->lchild);
  cout << T->data.key << " ";
  InOrderTraverse(T->rchild);
 }
}
int main(){
 cout << "请输入关键字" << endl;
 CreatBST(T);
 cout << "二叉排序树的中序遍历序列：" << endl;
 InOrderTraverse(T);
 int n;
 cout << "输入要查找的数据：" << endl;
 while(scanf("%d",&n) != EOF && n){
  if(SearchBST(T, n))
   cout << "输出查找的结果：该结点已找到。" << endl;
  else
   cout << "输出查找的结果：该结点未找到。" << endl;
 }
    return 0;
}

结果截图：

3. 编写DeleteBST(T, key)的伪代码实现从T中删除关键字key。如果无法编写出来，请写出在BST中删除关键字key所需注意的事项。

DeleteBST(T, key)的伪代码:

DeleteBST(T, key)
{
    if(T为空）
        return False;
    else
    {
        if(key==T->key)  //找到关键字等于key的数据元素
            return Delete(T);
        else if(key<T->key)
            return DeleteBST(在结点的左子树中搜索);
        else
            return DeleteBST(在结点的右子树中搜索）；
        }
}

BST中删除关键字key所需注意的事项:

首先找关键字，找到后要分三种情况，即，

1. 被删除的节点是叶子节点 ：直接删除该节点。删除的方法是在其双亲节点中相应的指针域的值改为空

2. 被删除的节点只有左子树或者只有右子树 ：也就是用其左子树或者右子树代替它。处理的方法是将其双亲节点的先欢迎指针域的值改为指向被删除节点的左子树或右子树

3. 被删除的节点既有左子树，又有右子树：采用的方法->（1）用前驱(左子树中最大的节点)的值直接替代当前的根节点的值，然后把前驱节点删除掉.（2）用后继(右子树中最#小的节点)的值直接替代当前的根节点的值，然后把后继节点删除掉。

二叉排序数的实现

原文：https://www.cnblogs.com/zghh/p/12732790.html