文件名称：二叉搜索树-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:09
数据结构 邓俊辉
第7章 搜索树 §7.2 事叉搜索树 220022 §7.2 二叉搜索树 7.2.1 顺序性 若二叉树中各节点所对应的词条之间支持大小比较，则在不致歧义的情况下，我们可以 不必严格区分树中的节点、节点对应的词条以及词条内部的关键码。于是如图7.2所示，若 对于树中任一节点r，左（右）子树中的节点（若存在）均不大于（不小于）r，则称之为二 叉搜索树（binary search tree）简而言之，即处处满足这种顺序性的二叉树。 图7.2 事叉搜索树即处处满足顸序性癿事叉树 为回避歧义情况，这里不妨暂且假定各节点所对应的词条互不相等。于是，二叉搜索树 的顺序性便可简化表述为：任一节点r的左（右）子树（若非空）均小于（大于）r。图7.3 给出了二叉搜索树的三个实例与三个反例，请对照这一性质逐个确认。 图7.3 事叉搜索树癿实例（左三）不反例（右三） 当然，在实际应用中，对相等元素的禁止既不自然也不必要。读者可在本书所给代码的 基础上继续扩充，使得二叉搜索树的接口支持相等词条的同时并存（习题[9]）。比如，在 去除掉这一限制之后，图7.3中原先的第一个反例，将转而成为合法的二叉搜索树。 7.2.2 中序遍历序列 图7.4 事叉搜索树癿中序遍历序列必然单调排列