【数据结构】二叉排序树

---

一、关于二叉排序树

二叉排序树的特点：中序遍历的顺序是有序的。

中序遍历结果：12 16 23 35 42 60
逆中序遍历结果：60 42 35 23 16 12

二、二叉排序树结构设计

Bst.h

#ifndef BST_H
#define BST_H
//二叉搜索树（二叉排序树）
	//三叉链式结点
typedef int ElemType;
typedef struct BstNode
{
	ElemType key;
	struct BstNode* leftchild;
	struct BstNode* rightchild;
	struct BstNode* parent;

}BstNode, *BstTree;

#endif

三、二叉排序树的使用

（1）申请节点

//申请结点
BstNode* BuyNode()
{
	BstNode* node = (BstNode*)malloc(sizeof(BstNode));
	if (NULL == node) return NULL;
	memset(node, 0, sizeof(BstNode));
	return node;
}

（2）插入节点

//二叉搜索树insert插入结点
/*
ptr是指针的引用：底层 == 二级指针 const BstNode**
*/
bool Insert(BstNode*& root, ElemType val)
{	
	//第一次插入结点
	if (root == NULL)
	{
		root = BuyNode();
		root->key = val;
		return true;
	}
	BstNode* pa = NULL;
	BstNode* ptr = root;
	while (ptr != NULL && ptr->key != val)
	{
		pa = ptr;
		ptr = val < ptr->key ? ptr->leftchild : ptr->rightchild;
	}
	//重复值
	if (ptr != NULL && ptr->key == val)
	{
		return false;
	}
	//不是重复值 ptr == NULL需要插入pa的两边
	ptr = BuyNode();
	ptr->key = val;
	ptr->parent = pa;
	if (ptr->key < pa->key)
	{
		pa->leftchild = ptr;
	}
	else
	{
		pa->rightchild = ptr;
	}
	return true;
}

（3）找第一个结点（最小值）

//第一个（最小值）
BstNode* First(BstNode* ptr)
{
	while (ptr != NULL && ptr->leftchild != NULL)
	{
		ptr = ptr->leftchild;
	}
	return ptr;
}

（4）找最后一个结点（最大值）

//最后一个(最大值)
BstNode* Last(BstNode* ptr)
{
	while (ptr != NULL && ptr->rightchild != NULL)
	{
		ptr = ptr->rightchild;
	}
	return ptr;
}

（5）找后一个结点（较大者）

//寻找当前结点的较大的结点
BstNode* Next(BstNode* ptr)
{
	if (ptr == NULL)
		return NULL;
	if (ptr->rightchild != NULL)
	{
		return First(ptr->rightchild);
	}
	else//ptr->rightchild == NULL
	{
		BstNode* pa = ptr->parent;
		while (pa != NULL && ptr == pa->rightchild)
		{
			ptr = pa;
			pa = ptr->parent;
		}
		return pa;
	}
}

（6）找前一个结点（较小者）

//寻找前驱，较小一个的结点
BstNode* Prev(BstNode* ptr)
{
	if (ptr == NULL)
		return NULL;
	if (ptr->leftchild != NULL)
	{
		return First(ptr->leftchild);
	}
	else
	{
		BstNode* pa = ptr->parent;
		while (pa != NULL && ptr == pa->leftchild)
		{
			ptr = pa;
			pa = ptr->parent;
		}
		return pa;
	}
}

（7）非递归中序遍历

//非递归的中序遍历:从小到大
void MidOrder(BstNode* root)
{
	for (BstNode* ptr = First(root); ptr != NULL; ptr = Next(ptr))
	{
		cout << ptr->key << " ";
	}
	cout << endl;
}

（8）非递归逆中序遍历

//逆序中序遍历 从大到小
void ReMidOrder(BstNode* root)
{
	for (BstNode* ptr = Last(root); ptr != NULL; ptr = Prev(ptr))
	{
		cout << ptr->key << " ";
	}
	cout << endl;
}

（9）清空二叉树

void Clear(BstNode* root)
{
	if (root != NULL)
	{
		Clear(root->leftchild);
		Clear(root->rightchild);
		delete root;
	}
}

（10）查找val

//查找
BstNode* FindValue(BstNode* ptr, ElemType val)
{
	if (ptr == NULL) return NULL;
	BstNode* pa = NULL;
	while (ptr != NULL && ptr->key != val)
	{
		pa = ptr;
		ptr = val < ptr->key ? ptr->leftchild : ptr->rightchild;
	}
	return ptr;
}

（11）删除val

//删除
bool Remove(BstNode*& ptr, ElemType val)
{
	if (ptr == NULL) return false;
	BstNode* pa = NULL;
	BstNode* res = FindValue(ptr, val);
	if (res == NULL) return false;

	//删除的是双分支结点(双分支转成叶子or单分支)
	if (res->leftchild != NULL && res->rightchild != NULL)
	{
		//找到仅大于res结点的结点
		BstNode* q = First(res);
		res->key = q->key;
		res = q;
	}
	pa = res->parent;
	//child是res的孩子：NULL or left or right
	BstNode* child = res->leftchild != NULL ? res->leftchild : res->rightchild;
	//删除单分支 root节点
	if (pa == NULL)
	{
		ptr = child;
	}
	else
	{
		//删除的单分支结点
		if (child != NULL)
		{
			child->parent = pa;
		}
		//叶子or单分支结点 pa->删除res 链接到child
		if (pa->leftchild == res)
		{
			pa->leftchild = child;
		}
		else
		{
			pa->rightchild = child;
		}
	}
	free(res);
	return true;
}

（12）测试

int main()
{
	int arr[] = {23, 32, 12, 35, 24, 56, 78, 45};
	int len = sizeof(arr) / sizeof(arr[0]);
	BstNode* root = NULL;
	for (int i = 0; i < len; ++i)
	{
		Insert(root, arr[i]);
	}
	MidOrder(root);
	ReMidOrder(root);

	Remove(root, 56);
	MidOrder(root);
	Clear(root);
	return 0;
}