跳转至

树的遍历

普通树

深度优先

对于一个结点，遍历完我们优先拓展深度。一般采用递归或栈来实现。例如，以下图的深度优先遍历顺序为：\(1-2-5-4-3-6\)。

void dfs(int x) {
  cout << x << ' ';
  for (int i : e[x]) {
    dfs(x);
  }
}

void dfs(int x) {
  stack<int> s;
  for (s.push(x); s.size(); ) {
    int t = s.top();
    s.pop();
    for (int i : e[x]) {
      s.push(i);  // 注意这里遍历儿子的顺序是反的
    }
  }
}

广度优先

也称层序遍历。每一次都遍历一整层，一般使用队列实现。例如上图的广度优先遍历的顺序为：\(1-2-3-5-4-6\)。

void bfs(int x) {
  queue<int> q;
  for (q.push(x); q.size(); q.pop()) {
    cout << q.front() << ' ';
    for (int i : e[q.front()]) {
       q.push(i);
    }
  }
}

对于无根树

由于没有指定的根，因此我们在存储时也不知道谁是谁的什么，那么我们只能双向存储。因此在遍历时，我们需要记录一个结点的前继是谁，然后在遍历儿子的时候去掉这个前继。

void dfs(int x, int f) {
  cout << x << ' ';
  for (int i : e[x]) {
    if (i != f) {
      dfs(i, x);
    }
  }
}

void bfs(int x, int f) {
  queue<pair<int, int>> q;
  for (q.emplace(x, f); q.size(); q.pop()) {
    cout << q.front().first << ' ';
    for (int i : e[q.front().first]) {
      if (i != q.front().second) {
        q.emplace(i, q.front().first);
      }
    }
  }
}

二叉树

先序遍历

先遍历根结点，然后遍历左子树，接着遍历右子树。通俗一点讲就是“根左右”。最上面我给的图就是一颗二叉树，先序遍历顺序为：\(1-2-5-4-3-6\)。

void dfs(int x) {
  cout << x << ' ';
  if (t[x].l) {
    dfs(t[x].l);
  }
  if (t[x].r) {
    dfs(t[x].r);
  }
}

中序遍历

先遍历左子树，再遍历根结点，最后遍历右子树。通俗一点讲就是“左根右”。上图中序遍历顺序为：\(5-2-4-1-3-6\)。

void dfs(int x) {
  if (t[x].l) {
    dfs(t[x].l);
  }
  cout << x << ' ';
  if (t[x].r) {
    dfs(t[x].r);
  }
}

后序遍历

先遍历左子树，再遍历右子树，最后遍历根结点。通俗一点讲就是“左右根”。上图中序遍历顺序为：\(5-4-2-6-3-1\)。

void dfs(int x) {
  if (t[x].l) {
    dfs(t[x].l);
  }
  cout << x << ' ';
  if (t[x].r) {
    dfs(t[x].r);
  }
}

评论