Question

构造一个二叉排序树

有一串数字{12、5、17、3、5、14、20、9、15、8、10} 要构成一棵二叉排序树 怎么构造？有两个5，该怎么排 为什么

Answer 1

二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 它的左、右子树也分别为二叉排序树。

Answer 2

看了百度知道之前有人回答 “二叉排序树的插入 如果遇到 相同的节点 怎么办”，你也可以看一下该问题的答案，个人觉得挺有道理的。
根据这个结论，该二叉树这样排
12
/ \
5 17
/ \ / \
3 5 14 20
\ \
9 15
/ \
8 10
或者
12
/ \
5 17
/ \ / \
3 9 14 20
\ / \ \
5 8 10 15
都可以，看你的要求，只要中序遍历是递增即可。上述两个中序遍历都是
3 5 5 8 9 10 12 14 15 17 20

Answer 3

二叉树的基本概念可以了解一下

二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值

• 若右子树不空，则右字数上所有节点的值均大于它的根节点的值
  

• 它的左、右子树也分别为二叉排序数（递归定义）
  

从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）


所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）