| 二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，即每读入一个元素，首先在二叉查找树中进行查找，若找到则不再插入，否则根据查找时得到的位置信息进行插入。其过程为：若二叉查找树为空，则为新元素创建结点并作为二叉查找树的根结点；若二叉查找树非空，则将新元素的值与根结点的值相比较，如果小于根结点的值，则继续在左子树中查找，否则在右子树中继续查找，直到某结点的值与新元素的值相等，或者到达空的子树为止，此时创建新元素的结点并替换该空的子树完成插入处理。设关键字序列为｛46，25，54，13，29，91｝，则对应的二叉查找树构造过程如下图（a）~（g）所示。
|
|
|
|
|
|
|
| 从上面的插入过程还可以看到，每次插入的新结点都是二叉查找树上新的叶子结点，因此在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针域，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。
|
|
|
| 另外，由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉查找树是一棵单枝树。从二叉查找树的查找过程可知，这种情况下的查找效率与顺序查找的效率相当。
|
|
|
