二叉树的序列化

[编程题]二叉树的序列化

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

二叉树被记录为文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化，给定一颗二叉树，请将该二叉树先序序列化和层序序列化。

假设序列化的结果字符串为 str，初始时 str = ""，遍历二叉树时，遇到 null 节点，则在 str 的末尾加上 "#!"，否则加上"当前的节点值!"。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

输出两行分别表示该二叉树的先序序列化和层序序列化

示例1

输入

2 1
1 2 0
2 0 0

输出

1!2!#!#!#!
1!2!#!#!#!

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

#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) {
    fprintf(stdout, "#!");
    return;
  }
  fprintf(stdout, "%d!", root_id);
  preorder(infos, infos[root_id].l_child);
  preorder(infos, infos[root_id].r_child);
}

void levelOrder(INFO infos, Id root_id) {
  // corner case
  if (!root_id) return;
  
  Id* q = (Id*) malloc(2E6 * sizeof(Id));
  if (!q) exit(0);
  
  size_t front = 0, rear = 0;
  *(q + rear++) = root_id;
  
  Id cur;
  while (front < rear) {
    cur = *(q + front++);
    if (cur) {
      fprintf(stdout, "%d!", cur);
      *(q + rear++) = infos[cur].l_child;
      *(q + rear++) = infos[cur].r_child;
    } else
      fprintf(stdout, "#!");
  }
}

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), levelOrder(infos, root_id);
  return 0;
}

发表于 2021-08-03 18:31:24 回复(0)