二叉排序树的中序遍历就是按照关键字的从小到大顺序输出（先序和后序可没有这个顺序）
一、以序列 6 8 5 7 9 3构建二叉排序树：
二叉排序树就是中序遍历之后是有序的；
构造二叉排序树步骤如下；
插入法构造：
2、
以此类推 将要插入的结点先跟根结点比较， 比根结点大进入右子树 反之进入 左子树；
在跟进入的 左子树（右子树）的结点比较 方法同上；
直到没有结点了 在插入； 你给的排序最后的二叉排序树如下；
中序遍历结果是 ： 3 4 5 6 7 8 9 ；
先序遍历结果是 ： 6 4 3 5 8 7 9 ；
建立二叉排序树后进行查找，则等概率情况下查找成功的平均查找长度为（1+2*2+4*3）/7=17/7
例题：
已知长度为9的表16、3、7、11、9、26、18、14、15，建立二叉排序树后进行查找，则等概率情况下查找成功的平均查找长度为（31/9）
本题考查二叉排序树的查找。
二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质(BST性质)的二叉树：
(1)若它的左子树非空，则左子树上所有结点的值均小于根结点；
(2)若它的右子树非空，则右子树上所有结点的值均大于根结点；
(3)左、右子树本身又各是一棵二叉排序树。
在做该题时，首先将表中的9个元素放进二叉树中构成二叉排序树，在构造二叉排序树时，我们将表中的元素依次按照构造二叉排序树的规则往树中添加元素，在获得二叉排序树后，计算平均长度就变得简单了，为(1+2+2+3+3+4+5+5+6)/9=31/9。
二、二叉树的先序、中序、后序遍历
前序遍历：根节点->左子树->右子树（根->左->右）
中序遍历：左子树->根节点->右子树（左->根->右）
后序遍历：左子树->右子树->根节点（左->右->根）
举个例子：
这棵树的前序遍历为：ABDEGHCF
中序遍历：左子树—> 根结点 —> 右子树（在中间遍历根节点）
这棵树的中序遍历为：DBGEHACF
后序遍历：左子树 —> 右子树 —> 根结点（最后遍历根节点）
这棵树的后序遍历为：DGHEBFCA
（1）若树T为空树，则其括号表示为空
（2）若树T只包含一个结点，则其括号表示即为该结点本身
（3）若树T由根结点A和它的m棵子树T1,T2,...,Tm构成，则其括号表示为：A(T1的括号表示，T2的括号表示,... ,Tm的括号表示)
其中，子树的括号表示同样应该遵循以上规则
实例：
