遍历规则
按照某种次序访问树中各节点,每个节点被访问恰好一次
T = V ∪ L ∪ R
遍历结果 ~ 遍历过程 ~ 遍历次序 ~ 遍历策略
先序 | 中序 | 后序 | 层次(广度) |
---|---|---|---|
V 丨 L 丨 R | L 丨 V 丨 R | L 丨 R 丨 V | 自上而下,先左后右 |

递归
template <typename T, typename VST>
void traverse(BinNodePosi(T) x, VST &visit) {
if (!x) return;
visit(x -> data);
traverse(x -> lChild, visit);
traverse(x -> rChild, visit);
} // T(n) = O(1) + T(a) + T(n-a-1) = O(n)

迭代1
算法
template <typename T, typename VST>
void travPre_I1(BinNodePosi(T) x, VST &visit) {
Stack <BinNodePosi(T)> S; // 辅助栈
if (x) S.push(x); // 根节点入栈
while (!S.empty()) { // 栈变空之前反复循环
x = S.pop(); visit(x -> data); // 弹出并访问当前节点
if (HasRChild(*x)) S.push(x -> rChild); // 右孩子先入后出
if (HasLChild(*x)) S.push(x -> lChild); // 左孩子后入先出
}
}
实例

迭代2
思路

构思

算法
template <typename T, typename VST> // 分摊 O(1)
static void visitAlongLeftBranch(
BinNodePosi(T) x, VST &visit, Stack <BinNodePosi(T)> &S)
{
while (x) { // 反复地
visit(x -> data); // 访问当前节点
S.push(x -> rChild); // 右孩子(右子树)入栈(将来逆序出栈)
x = x -> lChild; // 沿左侧链下行
}
}
template <typename T, typename VST>
void travPre_I2(BinNodePosi(T) x, VST &visit) {
Stack <BinNodePosi(T)> S; // 辅助栈
while (true) { // 以(右)子树为单位,逐批访问节点
visitAlongLeftBranch(x, visit, S); // 访问子树 x 的左侧链,右子树入栈缓冲
if (S.empty()) break; // 栈空即退出
x = S.pop(); // 弹出下一子树的根
} // #pop = #push = #visit = O(n) = 分摊 O(1)
}
实例

本文由
Oscaner 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: 2019-05-05 08:35 星期日