文章目录
常见的树型查找表
常见的树型查找表由：二叉查找树、红黑树、B-树。
本文以二叉查找树为例，介绍树表查找。二叉查找树具有可动态插入关键码(key), 插入关键码时无需移动其他记录，树的数据有序，这3个特点。二叉树中，左子树的关键码都小于根结点的关键码，右子树的关键码都大于根结点的关键码。
二叉查找树–查找
在二叉查找树中查找，类似于折半查找（因为数据有序）。先比较给定值与根结点的关键码，如果相等，则查找成功。如果给定值<关键码，则进入左子树查找。若左子树为空，则查找失败，如果非空，则以左子树的根结点更新关键码，重复①-④。如果给定值>关键码，则进入右子树查找，若右子树为空，则查找失败，如果非空，则以右子树的根结点更新关键码，重复①-④。
二叉树插入
二叉查找树插入，就是在二叉查找树查找失败为前提，将给定值插入到空子树。例如，查找到左子树为空，此时查找失败，则将给定值作为左子树插入。二叉查找树的形态会由输入给定值的顺序决定，如果输入的给定值本身就有序，则会构造出单枝树（即只有左子树,或只有右子树）。