知识卡片

普通读书笔记卡 · 5654.c.3.e.1

搜索树中序遍历得到升序

理解等级:中级

中序先访问左子树,再访问根,最后访问右子树;结合搜索树的全子树大小范围,每次都会在合适位置输出当前最小的未访问键,结果为升序。

访问全部n节点仍需线性时间,不能因单次查找可能对数就把输出全体也算对数。这个性质依赖搜索树不变量,普通二叉树的中序序列不保证有序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      二叉 搜索树的中序遍历序列是升序的 。 利用中序遍历升序的性质,我们在二叉搜索树中获取有序数据仅需 时间,无须进行额外的排序操作, 非常高效。 图7‑22 二叉搜索树的中序遍历序列 第7 章 树 hello‑algo.c

    参考来源

    - 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[6897,7007)) - 结论依据:原文中序有序论证与图7-22实际展开。 - 原始内容:二叉 搜索树的中序遍历序列是升序的 。 利用中序遍历升序的性质,我们在二叉搜索树中获取有序数据仅需 时间,无须进行额外的排序操作, 非常高效。 图7‑22 二叉搜索树的中序遍历序列 第7 章 树 hello‑algo.c