数据结构和算法笔记 (1) —— 二叉树的遍历

发表于 更新于 分类于 阅读次数：

树的遍历：按照某种次序访问树中各节点，每个节点被访问恰好一次

遍历方法：

  • 深度优先：先访问子节点，再访问父节点。按照根节点相对于左右子节点的访问顺序，分为前序 (Pre-order)、中序 (In-order) 和后序 (Post-order)
  • 广度优先：层次遍历

二叉树节点的定义如下

1
2
3
4
5
6
7
8
template <typename T>
struct TreeNode {
  T data_;
  std::shared_ptr<TreeNode<T>> left_;
  std::shared_ptr<TreeNode<T>> right_;

  TreeNode(T x) : data_(x), left_(nullptr), right_(nullptr) {}
};

前序遍历

遍历顺序：根 => 左 => 右

递归实现

1
2
3
4
5
6
7
8
9
10
template <typename T, typename VST>
void pre_order_traversal(std::shared_ptr<TreeNode<T>> node, VST& visit) {
  if (!node) {
    return;
  }

  visit(node);
  pre_order_traversal(node->left_, visit);
  pre_order_traversal(node->right_, visit);
}

迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T, typename VST>
void pre_order_traversal(std::shared_ptr<TreeNode<T>> root, VST& visit) {
  std::stack<decltype(root)> stk;
  auto node = root;

  while (node || !stk.empty()) {
    while (node) {
      visit(node);

      stk.push(node);
      node = node->left_;
    }

    if (!stk.empty()) {
      node = stk.top();
      stk.pop();

      node = node->right_;
    }
  }
}

中序遍历

遍历顺序：左 => 根 => 右

递归实现

1
2
3
4
5
6
7
8
9
10
template <typename T, typename VST>
void in_order_traversal(std::shared_ptr<TreeNode<T>> node, VST& visit) {
  if (!node) {
    return;
  }

  in_order_traversal(node->left_, visit);
  visit(node);
  in_order_traversal(node->right_, visit);
}

迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T, typename VST>
void in_order_traversal(std::shared_ptr<TreeNode<T>> root, VST& visit) {
  std::stack<decltype(root)> stk;
  auto node = root;

  while (node || !stk.empty()) {
    while (node) {
      stk.push(node);
      node = node->left_;
    }

    if (!stk.empty()) {
      node = stk.top();
      stk.pop();

      visit(node);

      node = node->right_;
    }
  }
}

后序遍历

遍历顺序：左 => 右 => 根

递归实现

1
2
3
4
5
6
7
8
9
10
template <typename T, typename VST>
void post_order_traversal(std::shared_ptr<TreeNode<T>> node, VST& visit) {
  if (!node) {
    return;
  }

  post_order_traversal(node->left_, visit);
  post_order_traversal(node->right_, visit);
  visit(node);
}

迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename T, typename VST>
void post_order_traversal(std::shared_ptr<TreeNode<T>> root, VST& visit) {
  std::stack<std::pair<decltype(root), bool>> stk;
  stk.push(std::make_pair(root, false));

  while (!stk.empty()) {
    auto node = stk.top().first;
    auto visited = stk.top().second;
    stk.pop();

    if (!node) {
      continue;
    }

    if (visited) {
      visit(node);
    } else {
      stk.push(std::make_pair(node, true));
      stk.push(std::make_pair(node->right_, false));
      stk.push(std::make_pair(node->left_, false));
    }
  }
}

层次遍历

遍历顺序：自上而下、先左后右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T, typename VST>
void level_traversal(std::shared_ptr<TreeNode<T>> root, VST& visit) {
  std::queue<decltype(root)> que;
  if (root) {
    que.push(root);
  }

  while (!que.empty()) {
    auto node = que.front();
    que.pop();

    visit(node);

    if (node->left_) {
      que.push(node->left_);
    }
    if (node->right_) {
      que.push(node->right_);
    }
  }
}