typedef int KeyType;
typedef struct BstNode
{
	struct BstNode* leftchild;//指向左孩子
	struct BstNode* parent;//指向双亲
	struct BstNode* rightchild;//指向右孩子
	KeyType key;//值value
}BstNode;

typedef struct
{
	BstNode* head;
	int cursize;
}BSTree;

我们将这种结构对应到上述图示的BST树中就是：

其中黑色的线所指的是自己的左右孩子结点
红色的线所指的是自己的双亲结点
绿色结点为这个BST树的头结点，它的值value为随机值，双亲节点指向BST树的根结点，左孩子指向这个BST树的最小值，右孩子指向这个BST树的最大值。
cursize代表这个BST数结点的个数，其不包括头结点。

开辟内存和初始化

struct BstNode* Buynode()
{
	struct  BstNode* s = (struct BstNode*)malloc(sizeof(struct BstNode));
	if (NULL == s) exit(EXIT_FAILURE);
	memset(s, 0, sizeof(struct BstNode));
	return s;
}

void Freenode(struct BstNode* p)
{
	free(p);
}

void Init_BSTree(BSTree* ptree)
{
	assert(ptree != NULL);
	ptree->cursize = 0;
	ptree->head = Buynode();
}

实现BST树的中序遍历

这个BST树的中序遍历结果是9 17 23 45 53 65 78 81 87 88 94

下面这个函数就是寻找某一节点前驱的函数，例如53的前驱节点就是45

struct BstNode* First(struct BstNode* ptr)//寻找ptr的前驱节点
{
	while (ptr != NULL && ptr->leftchild != NULL)
	{
		ptr = ptr->leftchild;
	}
	return ptr;
}

下面函数是寻找某一节点后继的函数，例如53的后继节点就是65

struct BstNode* Next(BSTree* ptree, struct BstNode* ptr)//寻找后继节点
{
	if (ptr == NULL) return NULL;
	if (ptr->rightchild != NULL)
	{
		return First(ptr->rightchild);
	}
	else
	{
		struct BstNode* pa = ptr->parent;
		while (pa != ptree->head && ptr != pa->leftchild)
		{
			ptr = pa;
			pa = ptr->parent;
		}
		if (pa == ptree->head)
		{
			pa = NULL;
		}
		return pa;
	}
}

以下是中序遍历的函数

void NiceInOrder(BSTree* ptree)//中序遍历BST树
{
	assert(ptree != NULL);
	for (struct BstNode* p = First(ptree->head->parent); p != NULL; p = Next(ptree, p))
	{
		std::cout << p->key << "  ";
	}
	std::cout <<std:: endl;
}

实现BST树的插入操作

现在我们要将值为100的节点插入到BST树中

首先，让100与根节点53进行比较，100>53，则100应插入到节点53的右子树
接着，让100与节点点78进行比较，100>78，则100应插入到节点78的右子树
接着，让100与节点87进行比较，100>87，则100应插入到节点87的右子树
接着，让100与节点94进行比较，100>94，则100应插入到节点94的右子树
最后，节点94的右子树为空，则让节点94的右孩子指向100，100的双亲指向94，此时BST树的最大节点为100，因此让头结点的右孩子指向100。

结果如下图：

bool Insert(BSTree* ptree, KeyType kx)
{
	if (ptree->head->parent == NULL) //当是一棵空树时
	{
		struct BstNode* root = Buynode();
		root->key = kx;
		ptree->head->parent = root;
		ptree->head->leftchild = root;
		ptree->head->rightchild = root;
		root->parent = ptree->head;
		ptree->cursize += 1;
		return true;
	}
	struct BstNode* pa = ptree->head;       // head
	struct BstNode* p = ptree->head->parent; // root;
	while (p != NULL && p->key != kx)
	{
		pa = p;
		p = kx < p->key ? p->leftchild : p->rightchild;
	}
	if (p != NULL && p->key == kx) return false;
	p = Buynode();
	p->key = kx;
	p->parent = pa;
	if (p->key < pa->key)
	{
		pa->leftchild = p;
		if (p->key < ptree->head->leftchild->key)
		{
			ptree->head->leftchild = p;
		}
	}
	else
	{
		pa->rightchild = p;
		if (p->key > ptree->head->rightchild->key)
		{
			ptree->head->rightchild = p;
		}
	}
	ptree->cursize += 1;
	return true;
}

实现BST树的删除操作

当我们想要删除BST树中的某一个节点时，一般会分为以下几种情况

（1）BST树为空树，则返回false;

（2）BST树不为空树，但要删除的节点不存在于BST树中，则返回fasle

（3）BST树不为空树，要删除的节点为叶子节点（例如上图中的节点9,23,65,81,88），则直接删除该节点，并重新判断头节点head的左右孩子指向。例如删除节点23

（4）BST树不为空树，要删除的节点为单支节点（例如上图中的节点45,94），则直接删除该节点，并用它的左孩子或右孩子节点替换它，最后再重新判断头节点head的左右孩子指向

例如删除节点45

（5）BST树不为空树，要删除的节点为双分支节点（例如上图中的节点53,17,78,87），则直接删除该节点，并用它的后继节点替换它，最后再重新判断头节点head的左右孩子指向。之所以要用后继节点替换，是因为当我们中序遍历BST树时，最终得到的结果是从小到大排序的，只有用后继节点替换被删除的节点，这一特征才不会破坏。

例如，当我们要删除节点78时，会用节点81来替换78，因为这个BST树的中序遍历结果是【9,17,23,45,53,65,78,81,87,88,94】，78的后继是81。这样就算78被删除了，最后的中序遍历结果【9,17,23,45,53,65,81,87,88,94】依然是正确的。

（6）BST树不为空树，如果要删除的节点为根结点，则可以用根结点的前驱节点或者后继节点来替换根结点

例如：用根结点的后继节点替换根结点

用根结点的前驱节点替换根结点

/*删除*/
/*p是要删除的节点
pa是p的根节点*/
bool Remove(BSTree* ptree, KeyType kx)/*该删除函数并没有维护头结点左右孩子指向的的代码*/
{
	if (ptree->head->parent == NULL) return false;//没有根

	struct BstNode* p = FindValue(ptree, kx);
	if (p == NULL) return false;

	/*删除时按中序遍历的规则继承被删除点的位置*/
	if (p->leftchild != NULL && p->rightchild != NULL)
	{
		struct BstNode* nt = Next(ptree, p);
		p->key = nt->key;
		p = nt;
	}
	struct BstNode* pa = p->parent;
	struct BstNode* child = p->leftchild != NULL ? p->leftchild : p->rightchild;
	if (child != NULL) child->parent = pa;
	if (pa == ptree->head)
	{
		pa->parent = p;
	}
	else
	{
		if (pa->leftchild == p)
		{
			pa->leftchild = child;
		}
		else
		{
			pa->rightchild = child;
		}
	}
	Freenode(p);
	ptree->cursize -= 1;
	return true;
}

实现BST树的查找操作

BST树的查找操作相对来说比较简单，我们分别用递归形式和非递归形式来实现

非递归

struct BstNode* FindValue(BSTree* ptree, KeyType kx)
{
	if (ptree == NULL) return NULL;
	struct BstNode* p = ptree->head->parent; // root;
	while (p != NULL && p->key != kx)
	{
		p = kx < p->key ? p->leftchild : p->rightchild;
	}
	return p;
}

递归

struct BstNode* Search(struct BstNode* ptr, KeyType kx)
{
	if (ptr == NULL || ptr->key == kx)
		return ptr;
	else if (kx < ptr->key)
		return Search(ptr->leftchild, kx);
	else
		return Search(ptr->rightchild, kx);
}
struct BstNode* SearchValue(BSTree* ptree, KeyType kx)
{
	struct BstNode* p = NULL;
	if (ptree != NULL)
	{
		p = Search(ptree->head->parent, kx);
	}
	return p;
}

码农公寓

BST树的定义

为什么 BST树又被称为二叉排序树

BST树的结构设计

开辟内存和初始化

实现BST树的中序遍历

实现BST树的插入操作

实现BST树的删除操作

实现BST树的查找操作

相关文章