C++ 数据结构 (五) 二叉树 (5) 先序遍历

1
2
3
4
5
6
7

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
2
3
4
5
6
7
8
9
10

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); // 左孩子后入先出
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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)
}