第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
输出三行,分别表示二叉树的先序,中序和后序。
3 1 1 2 3 2 0 0 3 0 0
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; }