C++ 数据结构 (五) 二叉树 (6) 中序遍历

1
2
3
4
5
6
7

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

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

template <typename T>
static void goAlongLeftBranch(BinNodePosi(T) x, Stack <BinNodePosi(T)> &S) {
  while (x) { S.push(x); x = x -> lChild; } // 反复地入栈, 沿左分支深入
}

template <typename T, typename V>
void travIn_I1(BinNodePosi(T) x, V &visit) {
  Stack <BinNodePosi(T)> S; // 辅助栈
  while (true) { // 反复地
    goAlongLeftBranch(x, S); // 从当前节点出发, 逐批入栈
    if (S.empty()) break; // 直至所有节点处理完毕
    x = S.pop();      // x 的左子树或为空, 或已遍历 (等效于空), 故可以
    visit(x -> data); // 立即访问之
    x = x -> rChild;  // 再转向其右子树 (可能为空, 留意处理手法)
  }
}