二叉排序树的构造过程二叉排序树( 二 )

二叉排序树的左右子树也要求都是二叉排序树；
二叉树排序二叉排序树就是中序遍历之后是有序的；
构造二叉排序树步骤如下；
插入法构造
第二个结点 4 比 6 来的小所以插入在 6 的左子树；
第三个结点 8 比 6 来的大所以插入在 6 的右子树；
第四个结点 5 比6 来得小先进入左子树然后跟 4比较，
5 比4 大所以插入在 4 的右子树；
以此类推将要插入的结点先跟根结点比较，比根结点大进入右子树反之进入左子树；
在跟进入的左子树（右子树）的结点比较方法同上；
直到没有结点了在插入；你给的排序最后的二叉排序树如下；
中序遍历结果是：3 4 5 6 7 8 9 ；
先序遍历结果是： 6 4 3 5 8 7 9 ；
什么是二叉排序树二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：
若左子树不空，则左子树上所有节点的值均小于它的根节点的值
若右子树不空，则右字数上所有节点的值均大于它的根节点的值
它的左、右子树也分别为二叉排序数（递归定义）
从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）
所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）

二叉排序树的构造过程 二叉排序树( 二 )

秒懂生活扩展阅读

二叉排序树的构造过程二叉排序树( 二 )