二叉排序树

一、SearchBST(T,key)与InsertBST(T,key)

SearchBST：

伪代码：

BiTNode *SearchBST(BiTNode *T, int key)
{
	if(T不为空||T->data等于key)
		返回 T；//找到或没找到的递归出口
	if（key<T->data）
		递归SearchBST(T->lchild,key);
	else
		递归SearchBST(T->rchild,key);
}

实现代码：

BiTNode *SearchBST(BiTNode *T, int key)
{
	if (T == NULL || T->data == key)//递归终结条件
		return T;
	if (key < T->data)
		return SearchBST(T->lchild, key);
	else
		return SearchBST(T->rchild, key);
}

InsertBST(T,key)：

伪代码：

int InsertBST(BiTNode*& T, int key)//插入成功返回1，插入失败返回0
{
    if(T为空)
    {
        为T申请空间；
        T->data=key;
        T->lchild=T->rchild为空;
        返回1；
    }
    else if(key==T->data)
        返回0;
    else if(key<T->data)
        递归左子树InsetBST(T->lchild,key);
    else
        递归右子树InsertBST(T->rchild,key);
}

实现代码：

int InsertBST(BiTNode*& T, int key)//插入成功返回1，插入失败返回0
{
	if (T == NULL)//树为空
	{
		T = new BiTNode;
		T->data = key;
		T->lchild = T->rchild = NULL;
		return 1;
	}
	else if (key == T->data)//存在相同关键字的节点返回0
		return 0;
	else if (key < T->data)
		return InsertBST(T->lchild, key);
	else
		return InsertBST(T->rchild, key);
}

二、CreateBST（T）

伪代码：

BiTNode* CreateNode(BiTNode* T)//根据每个数创建节点，结合insert函数实现树的创建
{
	int i;
	for (i = 0; i < 12; i++)
	{
		cin >> str[i];
	}
    for (i = 0; i < 12; i++)
    	InsertBST(T, str[i]);
    返回T;
}

实现代码：

BiTNode* CreateNode(BiTNode* T)
{
	int i;
	for (i = 0; i < 12; i++)
	{
		cin >> str[i];
	}
	for (i = 0; i < 12; i++)
		InsertBST(T, str[i]);//见本文“一”
	return T;
}

创建二叉排序树并中序输出完整代码：

#include<iostream>
using namespace std;
typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;
int InsertBST(BiTNode*& T, int key);
BiTNode* CreateNode(BiTNode* T);//创建新节点，返回结点指针
void InOrder(BiTNode* T);//中序遍历

int str[100];
int main()
{
	BiTNode* T = NULL;
	T=CreateNode(T);
	InOrder(T);
}
int InsertBST(BiTNode*& T, int key)//插入成功返回1，插入失败返回0
{
	if (T == NULL)//树为空
	{
		T = new BiTNode;
		T->data = key;
		T->lchild = T->rchild = NULL;
		return 1;
	}
	else if (key == T->data)//存在相同关键字的节点返回0
		return 0;
	else if (key < T->data)
		return InsertBST(T->lchild, key);
	else
		return InsertBST(T->rchild, key);
}
BiTNode* CreateNode(BiTNode* T)
{
	int i;
	for (i = 0; i < 12; i++)
	{
		cin >> str[i];
	}
	for (i = 0; i < 12; i++)
		InsertBST(T, str[i]);
	return T;
}
void InOrder(BiTNode* T)//中序遍历
{
	if (T->lchild != NULL)
		InOrder(T->lchild);
	printf("%d ", T->data);
	if (T->rchild != NULL)
		InOrder(T->rchild);
}

执行结果如下：

三、DeleteBST(T,key)(两个函数实现删除)

伪代码：

int DeleteBST(BiTNode* T, int key)
{
	if(T为空) 返回;
	else
	{
		if (key < T->data)
			递归DeleteBST(T->lchild, key);
		else if (key>T->data)
			递归DeleteBST(T->rchild, key);
		else
		{
			创建q;
			if (T->rchild为空)
			{
				q = T;
				T = T->lchild;
			}
			else if (T->lchild 为空)
			{
				q = T;
				T = T->rchild;
			}
			else
			{
				Delete(T, T->lchild);
			}
			InOrder(Keep);
			return 1;
		}
	}
}
void Delete(BiTNode* p, BiTNode*& r)
{
	创建q;
	if (r->rchild不为空)
		Delete(p, r->rchild);
	else
	{
		p->data = r->data;
		q = r;
		r = r->rchild;
		释放q;
	}
}

实现代码：

int DeleteBST(BiTNode* T, int key)
{
	if (T == NULL)
		return 0;
	else
	{
		if (key < T->data)
			return DeleteBST(T->lchild, key);
		else if (key>T->data)
			return DeleteBST(T->rchild, key);
		else
		{
			BiTNode* q;
			if (T->rchild == NULL)
			{
				q = T;
				T = T->lchild;
			}
			else if (T->lchild == NULL)
			{
				q = T;
				T = T->rchild;
			}
			else
			{
				Delete(T, T->lchild);
			}
			InOrder(Keep);
			return 1;
		}
	}
}
void Delete(BiTNode* p, BiTNode*& r)
{
	BiTNode* q;
	if (r->rchild != NULL)
		Delete(p, r->rchild);
	else
	{
		p->data = r->data;
		q = r;
		r = r->rchild;
		free(q);
	}
}

执行结果：

二叉排序树

原文：https://www.cnblogs.com/dcftx/p/12733056.html