二叉排序树的实现

1.

类型定义：

typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;

SearchBST(T, key)伪代码：

SearchBST(T, key) {
	if (T空) {
		return 0;
	}
	else
	{
		if (key < T->data) {
			向T的左孩子查找;
		}
		else {
			向T的有孩子查找;
		}
	}
	return T;
}

SearchBST(T, key)非递归实现代码：

SearchBST(T, key) {
	if (T==NULL) {
		return 0;
	}
	else {
		if (key < T->data) {
			T = T->lchild;
		}
		else {
			T = T->rchild;
		}
	}
	return T;
}

SearchBST(T, key)递归实现代码：

SearchBST(T, key) {
	if (T == NULL) {
		return 0;
	}
	else {
		if (T->data == key) {
			return T;
		}
		else if (T->data > key) {
			return SearchBST(T->lchild, key);
		}
		else {
			return SearchBST(T->rchild, key);
		}
	}
}

InsertBST(T, key)伪代码：

void InsertBST(BiTree T, int key) {
	BiTree p;
	为插入p节点创建结点空间;
	p->data = key;
	令p->lchild = p->rchild = NULL;
	if (T == NULL) {
		T = p;
	}
	else {
		if (T->data == p->data) {
			return;
		}
		else if (p->data< T->data) {
			将key插入到T的左孩子;
		}
		else {
			将key插入到T的右孩子;
		}

	}
}

InsertBST(T, key)递归实现代码：

viod InsertBST(BiTree T,int key) {
	BiTree p = new BiTNode;
	p->data = key;
	p->lchild = p->rchild = NULL;
	if (T == NULL) {
		T = p;
	}
	else {
		if (T->data == p->data) {
			return;
		}
		else if (p->data < T->data) {
			InsertBST(T->lchild, key);
		}
		else {
			InsertBST(T->rchild,key);
		}
	}
}

2.

CreateBST(T)的伪代码:

void CreateBST(BiTree T) {
	T = NULL;    //令树为空
	int i;
	for (i = 0; i < MaxSize; i++) {
		输入建树数据a;
		插入二叉树T;
	}
        return T;
}

CreateBST(T)的实现代码：

void CreateBST(BiTree T) {
	 T = NULL;
	int i;
	for (i = 0; i < MaxSize; i++) {
		int a;
		cin >> " " >> a;
		InsertBST(T, a);

	}
        return T;
}

控制台运行结果：

3.

DeleteBST(T, key)的伪代码：

int Delete(BiTree T) {
	BiTree q, s; 
	if (T->rchild == NULL) { 
		q = T; 
		重接T的左子树;
		free(q);
	}
	else if (T->lchild == NULL){ 
		q = T;
		重接它的右子树;
		free(q);
	}
	else{ 
		// 左右子树都不空
		q = T; 
		s = T->lchild;
		while (s->rchild) 
		{ 
			q = s;
			 向右到尽头，找到待删结点的前驱 ;
		} 
		将被删结点前驱的值T->data取代被删结点的值s->data;
		if (q != T)
			s的左子树重接 q 的右子树;
		else
			s的右子树重接 q 的左子树;
		free(s);
	}
	return 0;
}
int DeleteBST(BiTree T, int key)
{
	if (!T)
		return;
	else {
		if (key == T->data)
			return Delete(T);
		else if (key < T->data)
			return DeleteBST(T->lchild, key);
		else
			return DeleteBST(T->rchild, key);
	}
}

注意的事项:

1.二叉排序树删除结点并返回删除结点之后的树操作:
删除结点操作比查找，插入都麻烦，因为删除了一个结点，这棵树可能不满足二叉排序树的特点了，所以删除之前首先应该判断该结点的类型。

2.如果想要在删除结点操作后返回删除结点之后的树，直接修改完待删除结点及待删除结点的左右子树是不能返回删除结点之后的树的，这就需要先找到待删除结点的双亲，判断待删除结点是左孩子还是右孩子，然后在双亲结点的左孩子或右孩子位置续接修改之后的结点。

4.

使用代码实现DeleteBST(T, key):

int Delete(BiTree T) {
	BiTree q, s;
	if (T->rchild == NULL) {
			q = T;
		T = T->lchild;
		free(q);
	}
	else if (T->lchild == NULL) {
		q = T;
		T = T->rchild;
		free(q);
	}
	else {
		q = T;
		s = T->lchild;
		while (s->rchild)
		{
			q = s;
			s = s->rchild;
		}
		T->data = s->data;
		
		if (q != T)
			q->rchild = s->lchild;
		
		else 
			q->lchild = s->lchild;
		
		free(s);
	}
	return 0;
} 
int DeleteBST(BiTree T, int key)
{
	if (!T)
		return;
	else {
		if (key == T->data)
			return Delete(T);
		else if (key < T->data)
			return DeleteBST(T->lchild, key);
		else
			return DeleteBST(T->rchild, key);
	}
}

二叉排序树的实现

原文：https://www.cnblogs.com/fzhyxc520/p/12732359.html