定义

基本思想

定义

树表查找是对树型存储结构所做的查找。树型存储结构是一种多链表，该表中的每个结点包含有一个数据域和多个指针域，每个指针域指向一个后继结点。树型存储结构和树型逻辑结构是完全对应的，都是表示一个树形图，只是用存储结构中的链指针代替逻辑结构中的抽象指针罢了，因此，往往把树型存储结构(即树表)和树型逻辑结构(树)统称为树结构或树。在本节中，将分别讨论在树表上进行查找和修改操作的方法。

基本思想

⑴当二叉排序树不空时，首先将给定值k与根结点的关键字进行比较，若相等则查找成功；

⑵若给定值k小于根结点的关键字，则下一次与左子树的根结点的关键字进行比较，若给定值k大于根结点的关键字，则与右子树的根接到的关键字进行比较。如此递归的进行下去直到某一次比较相等，查找成功。如果一直比较到树叶都不等，则查找失败。