二叉树查找树（BST）模板

定义

二叉查找树的递归定义如下：

• 要么二叉查找树是一棵空树。

• 要么二叉查找树由根节点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上的所有结点的数据域均小于或等于根节点的数据域，右子树上的结点均大于根节点上的数据域。

又称为二叉搜索树，二叉排序树。

性质

1. 左子树<根结点<右子树。

2. 中序遍历顺序也是：左子树->根结点->右子树.所得到的中序序列是有序的。

3. 尽量减少树的高度（平衡二叉树（AVL））。

基本操作

1. 查找

2.插入

查找成功说明结点存在；查找失败的地方一定是需要插入的地方。只有root为NULL时插入。

3.建立

二叉查找树的建立就是先后插入n个结点的过程。

4.删除

思路一：
让比它大的最小结点覆盖它，然后删除比它大的最小结点。（后继：该结点右子树的最左结点）

思路二：
让比它小的最大结点覆盖它，然后删除比它小的最大结点。（前驱：该结点左子树的最右结点）

两个辅助函数：

删除函数：

hdu 3399 The order of a Tree

题目链接

题意：

构建二叉排序树 并输出它的前序遍历。

输入：

4
1 3 4 2

输出：

1 3 2 4

分析：

模拟BST的建树和访问。

代码：

参考：算法笔记 P310

二叉查找树（BST）模板

原文：https://www.cnblogs.com/hardworking-fairy/p/14681956.html