实现二叉树先序，中序和后序遍历

[编程题]实现二叉树先序，中序和后序遍历

热度指数：4413 时间限制：C/C++ 8秒，其他语言16秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

分别按照二叉树先序，中序和后序打印所有的节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

输出三行，分别表示二叉树的先序，中序和后序。

示例1

输入

输出

1 2 3
2 1 3
2 3 1

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

typedef int Id;

typedef struct {
  Id id;
  Id l_child, r_child;
} TreeNodeInfo, *INFO;

void preorder(INFO infos, Id root_id) {
  if (!root_id) return;
  fprintf(stdout, "%d ", root_id);
  preorder(infos, infos[root_id].l_child);
  preorder(infos, infos[root_id].r_child);
}

void inorder(INFO infos, Id root_id) {
  if (!root_id) return;
  inorder(infos, infos[root_id].l_child);
  fprintf(stdout, "%d ", root_id);
  inorder(infos, infos[root_id].r_child);
}

void postorder(INFO infos, Id root_id) {
  if (!root_id) return;
  postorder(infos, infos[root_id].l_child);
  postorder(infos, infos[root_id].r_child);
  fprintf(stdout, "%d ", root_id);
}

int main(const int argc, const char* const argv[]) {
  int n, root_id;
  fscanf(stdin, "%d %d", &n, &root_id);
  
  INFO infos = (INFO) malloc ((n + 1) * sizeof(TreeNodeInfo)) ;
  Id fa, l_ch, r_ch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    infos[fa].id = fa;
    infos[fa].l_child = l_ch;
    infos[fa].r_child = r_ch;
  }
  
  preorder(infos, root_id);
  fputc(10, stdout);
  
  inorder(infos, root_id);
  fputc(10, stdout);
  
  postorder(infos, root_id);
  return 0;
}

发表于 2021-08-03 18:44:06 回复(0)