Post

二叉树的构建与遍历

二叉树的构建与遍历

问题描述

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

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

    输入形式

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

    输出形式

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

样例输入

1
1(2(4,5),3)

样例输出

1
2
3
4 5 3
3 5 4
1 3 2 5 4

题解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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;
}
This post is licensed under CC BY 4.0 by the author.