知识卡片
中序遍历按键序输出
在二叉搜索树中依次遍历左子树、当前节点、右子树,就按非降序输出键,包括重复键。每个节点只访问常数次,所以 n 节点遍历为 Θ(n);树高主要影响递归深度,不把总访问量变成 Θ(n log n)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
Because of the binary-search-tree property, you can print out all the keys in a binary search tree in sorted order by a simple recursive algorithm
参考来源
- 位置:《算法导论(第4版)》第 12 章 12.1 节(`OEBPS/chapter012.xhtml`,文本字符 [0, 10000))。
- 结论依据:INORDER-TREE-WALK 依次递归左子树、输出 x.key、递归右子树;12.1 节给出含重复键的有序输出示例,定理 12.1 证明 n 节点遍历为 Θ(n)。
- 原始内容:Because of the binary-search-tree property, you can print out all the keys in a binary search tree in sorted order by a simple recursive algorithm