BST | 二叉排序树 | 二叉搜索树

目录

BST树的定义

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

BST树的结构设计

开辟内存和初始化

实现BST树的中序遍历

实现BST树的插入操作

 实现BST树的删除操作

实现BST树的查找操作


BST树的定义

BST树又被称为二叉排序树,二叉搜索树

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:

  • 每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同。(即BST树中所有元素的值不允许重复)
  • 左子树(如果存在)上所有结点的关键码都小于根结点的关键码。
  • 右孑树(如果存在)上所有结点的关键码都大于根结点的关键码。
  • 左子树和右子树也是二叉搜索树。

例如,下图所示的二叉树就是一个BST树

 BST | 二叉排序树 | 二叉搜索树

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

如果对一棵二叉搜索树进行中序遍历,可以按从小到大的顺序,将各结点关键码排列起来,所以也称二叉搜索树为二叉排序树。

BST树的结构设计

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 | 二叉排序树 | 二叉搜索树

  • 其中黑色的线所指的是自己的左右孩子结点
  • 红色的线所指的是自己的双亲结点
  • 绿色结点为这个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 | 二叉排序树 | 二叉搜索树

这个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树中

BST | 二叉排序树 | 二叉搜索树

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

结果如下图: 

BST | 二叉排序树 | 二叉搜索树

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

BST | 二叉排序树 | 二叉搜索树

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

例如删除节点45

BST | 二叉排序树 | 二叉搜索树

(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】依然是正确的。

BST | 二叉排序树 | 二叉搜索树

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

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

BST | 二叉排序树 | 二叉搜索树

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

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、TBT构建


下一篇:搬家第一天-1.WinccV7.3 使用VBS判断数据库Mydatabase下是否存在数据表Mytable