18-二叉查找树

17.7　二叉查找树

二叉查找树是一种结合了二分查找策略的链接结构。二叉树的每个节点都包含一个项和两个指向其他节点（称为子节点）的指针。图17.12演示了二叉查找树中的节点是如何链接的。二叉树中的每个节点都包含两个子节点——左节点和右节点，其顺序按照如下规定确定：左节点的项在父节点的项前面，右节点的项在父节点的项后面。这种关系存在于每个有子节点的节点中。进一步而言，所有可以追溯其祖先回到一个父节点的左节点的项，都在该父节点项的前面；所有以一个父节点的右节点为祖先的项，都在该父节点项的后面。图17.12中的树以这种方式存储单词。有趣的是，与植物学的树相反，该树的顶部被称为根（root）。树具有分层组织，所以以这种方式存储的数据也以等级或层次组织。一般而言，每级都有上一级和下一级。如果二叉树是满的，那么每一级的节点数都是上一级节点数的两倍。

二叉查找树中的每个节点是其后代节点的根，该节点与其后代节点构成称了一个子树（subtree）。如图17.12所示，包含单词 fate 、 carpet 和 llama 的节点构成了整个二叉树的左子树，而单词 voyage 是 style-plenum-voyage 子树的右子树。

假设要在二叉树中查找一个项（即目标项）。如果目标项在根节点项的前面，则只需查找左子树；如果目标项在根节点项的后面，则只需查找右子树。因此，每次比较就排除半个树。假设查找左子树，这意味着目标项与左子节点项比较。如果目标项在左子节点项的前面，则只需查找其后代节点的左半部分，以此类推。与二分查找类似，每次比较都能排除一半的可能匹配项。

我们用这种方法来查找 puppy 是否在图17.12的二叉树中。比较 puppy 和 melon （根节点项），如果 puppy 在该树中，一定在右子树中。因此，在右子树中比较 puppy 和 style ，发现 puppy 在 style 前面，所以必须链接到其左节点。然后发现该节点是 plenum ，在 puppy 前面。现在要向下链接到该节点的右子节点，但是没有右子节点了。所以经过3次比较后发现 puppy 不在该树中。

二叉查找树在链式结构中结合了二分查找的效率。但是，这样编程的代价是构建一个二叉树比创建一个链表更复杂。下面我们在下一个ADT项目中创建一个二叉树。