基于树的查找是将待查表组织成特定树的形式并在树结构上实现查找的方法，主要包括二叉排序树（binary sort tree）、平衡二叉树（balanced binary tree）和B-树等。

（1）二叉排序树的定义

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：

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

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

3）它的左、右子树也都分别是二叉排序树。

这是一个递归定义。由定义可以得出二叉排序树的一个重要性质；中序遍历一个二叉排序树时可以得到一个非递减有序序列。

（2）二叉排序树的查找

从其定义可见，二叉排序树的查找过程为：

1）若二叉排序树为空，查找失败。

2）若二叉排序树非空，将给定值k与二叉排序树的根结点的关键字比较。

3）若相等，查找成功，结束查找过程，否则，

    a）当给k小于根结点的关键字，则继续在左子树上进行查找，转1）。

b）当给k大于根结点的关键字，则继续在右子树上进行查找，转2）。

显然，这是一个递归过程。可用如下递归算法实现。

（3）二叉排序树的插入

根据动态查找表的定义，“插入”操作在查找不成功时才进行；若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

插入一个结点的过程为：设待插入结点的关键码为k，则 

1）若二叉排序树是空树，则k成为二叉排序树的根；

2）若二叉排序树非空，则将k与二叉排序树的根进行比较，如果k的值等于根结点的值，则停止插入；如果k的值小于根结点的值，则将k插入左子树；如果k的值大于根结点的值，则将k插入右子树。

构造一棵二叉排序树则是逐个插入结点的过程。