第9章-9.2动态查找表-9.2.1二叉排序树（附：修正一波原书算法的Bug问题）

二叉排序树，一种特殊的二叉树，在构造上面是完全符合二叉树的构造原理，但是，因为其独特的性质，也有一套自己的构造算法

二叉排序树定义：

• 空树是二叉排序树（单独）
• 它的左子树所有节点值均小于它的根节点值，且右子树所有的节点值均大于根节点值
• 左右子树也分别为二叉排序树

根据定义，利用递归构造二叉树的原理，增加条件实现递归操作即可：

如何访问递归二叉树的某个键值（颇有数据库检索风格）

KeyType key;
BiTree T;
T.data.key = key;

原则上记录项所属的数据类型错综复杂，若单一的数据项存在形式，则key就是数据本身，因此，选择最简单的数据类型进行验证操作即可

递归访问某个关键字

根据二叉排序树的排列原则，加入递归条件即可：

Status SearchBST(BiTree T, char key,BiTree f, BiTree& p)
{
	if (!T)
	{
		//f first given NULL
		p = f;
		return FALSE;
	}
	else if(key==T->data)
	{
		p = T;
		return TRUE;
	}
	else if(keydata)
	{
		return SearchBST(T->lchild, key, T, p);
	}
	else
	{
		return SearchBST(T->rchild, key, T, p);
	}
}

注意野指针问题，外部定义的全局T（树头指针）请务必有意义！

在查找某个键值时，T可能为空，则请在定义时，赋值为NULL，否则，该函数执行将出现问题（内存访问冲突：Vs2019操作规范）

如何构造二叉排序树？

二叉树的构造，最方便快捷且高效的操作就是“递归”！二叉排序树，顾名思义，则是有条件的递归，利用访问键值函数（上）

PS：访问键值函数的最终指针p会指向符合二叉排序树原则的最后一个元素节点上

因此，当存在键值元素e时，返回节点指针，不存在时，返回e应当在的位置的父指针，利用p指针执行连接操作即可

Status InsertBST(BiTree& T, TElemType e)
{
	BiTNode *p;
	if (!SearchBST(T, e, NULL,p))
	{
		BiTNode *s;
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = e;
		s->lchild = s->rchild = NULL;
		
		if (!p)
		{
			T = s;
		}
		else if LT(e, p->data)
		{
			p->lchild = s;
		}
		else
		{
			p->rchild = s;
		}
		return TRUE;
	}
	else
	{
		return FALSE;
	}
	return OK;
}

二叉排序树有何好处？

• 就是普通二叉树的受限类型
• 根节点和子树关系固定
• 中序遍历则可实现有序排列

因此，输入一个无序的序列（随意），再对该二叉树实现中序遍历，则可以得到该序列的有序序列（也可以进一步反转得到倒序）

排序操作变得简单！也不需要冒泡什么的了🤣

验证：

e = T->data;
printf("%c\n", e);

e = T->lchild->data;
printf("%c\n", e);

e = T->lchild->rchild->data;
printf("%c\n", e);