|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 查找 > 树表查找 >
|
|
相关知识点：3个
|
|
|
|
|
二叉查找树是一种动态查找表，其特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
|
|
|
|
根据定义，非空的二叉查找树中左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，因此，可将二叉查找树看成是一个有序表，其查找过程与折半查找过程相似。
|
|
|
|
在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找，否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到结点的路径；否则，查找过程终止于一棵空树。
|
|
|
|
设二叉查找树以二叉链表为存储结构，结点的类型定义如下：
|
|
|
|
|
|
|
|
|
