二叉树的构建与遍历

问题描述

假设二叉树中的每个结点值为单个整数，采用二叉链结构存储，假定每颗二叉树不超过2000个节点。设计算法完成

1. 按从左到右的顺序输出二叉树的叶子结点
2. 按从右到左的顺序输出二叉树的叶子结点
3. 输出二叉树所有的节点，按照从根节点开始，逐层输出，同一层按照从右向左的顺序

   输入形式

   每个测试是一颗二叉树的括号表示法字符串

   输出形式

   第一行是按从左到右的顺序输出二叉树的叶子结点，结点之间用空格隔开 第二行是按从右到左的顺序输出二叉树的叶子结点，结点之间用空格隔开 第三行是输出二叉树所有的节点，按照从根节点开始，逐层输出，同一层按照从右向左的顺序，结点之间用空格隔开

样例输入

1(2(4,5),3)

样例输出

4 5 3
3 5 4
1 3 2 5 4

题解

这是作者数据结构课的作业，属于是最基础的二叉树构建、dfs和bfs。这道题选择使用数组链表来进行构建，不得不说这种构建方式真是十分美妙。由于获取到的是一个字符串表达式，我们可以用指针来对这一个串进行递归，这里用到了*&，即对指针的引用，这为递归提供了很大的便利。

#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010;

/* l数组表示当前节点的左节点，r数组同理，e表示节点值，q为后面用到的队列 */
int l[N], r[N], e[N], q[N], root, idx;
char line[N];

int pars(char *&s) {
  if (*s == '\0' || !isdigit(*s)) return 0;

  int u = ++idx;
  int val = 0;
  while (isdigit(*s)) {
    val = val * 10 + (*s - '0');
    s++;
  }
  e[idx] = val;
  if (*s == '(') {
    s++;
    l[u] = pars(s); // 先递归左树，后递归右树
    if (*s == ',') {
      s++;
      r[u] = pars(s);
    }
    if (*s == ')') {
      s++;
    }
  }

  return u;
}

void dfs1(int u) {
  if (!u) return;
  int left = l[u], right = r[u];
  if (!left && !right) {
    printf("%d ", e[u]);
    return;
  }
  dfs1(left);
  dfs1(right);
}

void dfs2(int u) {
  if (!u) return;
  int left = l[u], right = r[u];
  if (!left && !right) {
    printf("%d ", e[u]);
    return;
  }
  dfs2(right);
  dfs2(left);
}

/* 队列实现bfs */
void bfs(int u) {
  int hh = 0, tt = 0;
  q[0] = u;

  while (hh <= tt) {
    int v = q[hh++];
    if (v) {
      q[++tt] = r[v];
      q[++tt] = l[v];
      printf("%d ", e[v]);
    }
  }

  puts("");
}

int main() {
  // freopen("in.txt", "r", stdin);
  memset(line, 0, sizeof line);
  scanf("%s", line);
  char *input = line;
  root = pars(input);
  dfs1(root);
  puts("");
  dfs2(root);
  puts("");
  bfs(root);
  return 0;
}