二叉排序树的实现

一.编写SearchBST(T, key)与InsertBST(T, key)的伪代码

1.SearchBST(T, key)伪代码:

SearchBST(T, key)
{
    if(T为空||T值=key)
        return T;
    if(T值<key)
        递归遍历左子树查找k;
    else
        递归遍历右子树查找K;
}

实现

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

2.InsertBST(T, key)伪代码:

InsertBST(T, key)
{
    if(T为空)
     创建新节点为根节点;
     return 真;
    else if (T值==key) 
     return 假;
    else if(key<T值)
     插到左子树中；
    else 
     插到右子树中；   
}

实现

InsertBST(T, key)
{
    if(T==null)
    {
     T=new BSTNode;
     T->data=key;
     T->lchild=NULL;
     T->rchild=NULL;
        return true;
    }
    else if (T.data==key) 
    {
     return false;
    }
    else if(key<T.data)
    {
     return InsertBST(T->lchild, key);
    }
    else 
    {
     return InsertBST(T->rchild, key);
    }  
}

二.编写CreateBST(T)的伪代码实现从控制台输入创建BST树

1.CreateBST(T)伪代码:

CreateBST(T)
{
    初始化T为空树；
    关键字数组下标i=0
    while(i<n) 
    {
        调用插入算法；
    }
    return T;
}

2.创建BST树

1.控制台建BST树

2.BST树完整代码

#include<iostream>
#include<stdio.h>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct node
{
	KeyType k;
	InfoType data;
	struct node* lchild, * rchild;
}BSTNode, * BSTree;
bool InsertBST(BSTree& T, KeyType key)
{
	int i = 0;
	if (T == NULL)
	{
		T = new BSTNode;
		T->k = key;
		T->lchild = NULL;
		T->rchild = NULL;
		return true;
	}
	else if (T->k == key)
	{
		return false;
	}
	else if (T->k > key)
	{
		return InsertBST(T->lchild, key);
	}
	else
	{
		return InsertBST(T->rchild, key);
	}
}
BSTNode* CreateBST(int A[], int n)
{
	BSTree T = NULL;
	int i = 0;
	while (i < n)
	{
		InsertBST(T, A[i]);
		i++;
	}
	return T;
}
void InOrder(BSTree T)
{
	if (T)
	{
		InOrder(T->lchild);
		cout<<T->k<<" ";
		InOrder(T->rchild);
	}
}
int main()
{
	BSTree T;
	int A[100];
	int i;
	int key = 0;
	int n = 12;
	cout << "结点"<<endl;
	for (i = 0; i < n; i++)
	{
		cin>>A[i];
	}
	T = CreateBST(A, n);
	cout<<"中序输出"<<endl;
	InOrder(T);
	InsertBST(T, key);
	return 0;

}

实现

BSTNode* CreateBST(int A[], int n)
{
	BSTree T = NULL;
	int i = 0;
	while (i < n)
	{
		InsertBST(T, A[i]);
		i++;
	}
	return T;
}

三.编写DeleteBST(T, key)的伪代码实现从T中删除关键字key

1.DeleteBST(T, key)伪代码

DeleteBST(T, key)
{
    if(T为空)
     return 假；
    else
    {
      if(key=T值)
         删除T;
        return 真 
     else if(key<T值)
        递归左子树删除key;
     else
        递归左子树删除Key
    }
}

2.实现

bool DeleteBST(BSTNode T, KeyType key)
{
	if (T == NULL)
	{
		return false;
	}
	else
	{
		if (key = T->data)
		{
			delete(T);
			return true;
		}
		else if (key < T->data)
                 {
		    return DeleteBST(T->lchild, key);
                 }
		else
                 {
		    return DeleteBST(T->rchild, key);
                 }
	}
}

3.删除关键字key注意事项

(1)删除结点时不能把以该结点为根的子树全部删去
(2）删除后的二叉树要满足二叉排序树的性质
(3)二叉树在删除时必须先查找
(4)如果结点是叶子结点，那么直接删去
(5)如果非叶子结点要让下一个结点指向该结点前一个结点在删除

二叉排序树的实现

原文：https://www.cnblogs.com/Jyang666/p/12731442.html