知识卡片
搜索树中序遍历得到升序
中序先访问左子树,再访问根,最后访问右子树;结合搜索树的全子树大小范围,每次都会在合适位置输出当前最小的未访问键,结果为升序。
访问全部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