data-structures - 给定二叉树的先序二叉序列/排序，你能画出二叉树吗？

Question

二叉树(以及有序森林)可以表示为二进制字符串。二叉串是通过先序遍历二叉树得到的，每个节点记录一个1，每个空子树(空链接)记录一个0。

这意味着如果给我一棵二叉树，我可以进行前序遍历并生成二叉序列表示。

是否也可以相反？如果我得到这个二进制序列 11011000101101010001 ，我可以画二叉树吗？

Answer 1

是的你可以。

将内部节点标记为 a和外部的为 b ;当然你可以假设a如 0和 b如 1 (反之亦然)。但我认为区分字母比区分数字更容易(尽管“品味”这件事)。

如果您不知道什么是“外部节点”，那么您可以假设它们是 NULL指针。

现在，任何标记为我所说的树的前序遍历形成了一个属于 Lukasiewicz 语言的词。可以证明这个词是独一无二的。也就是说，对于任何一对树 t1和 t2 , code(t1) != code(t2) ;总是!此外(这应该是您关注霍夫曼编码的原因)，Lukasiewicz 语言是前缀。

例如，对于树



它的前序遍历是aaaabbabbaabbbababb或 000011011001110111
我把生成代码的代码留给你；这是一个先序遍历。如果您有兴趣反转它，即获得给定代码的树，那么这个试图回答您的问题的伪代码会这样做:

Node * code_to_tree(char *& code)
{
  if (*code++ == 'b')
    return nullptr;

  Node * p = new Node;
  LLINK(p) = code_to_tree(code);
  RLINK(p) = code_to_tree(code);

  return p;
}

在实际实现中，您将读取位。

上面的例程假设代码是正确的；也就是说，它是从二叉树生成的。请注意，并非所有由 a 组成的词的和 b属于 Lukasiewicz 语言。但是可以对它们应用一些可显示的规则。

一、数量b的必须正好是 a 的数目加一。二、如果每个a权重一 (1) 并且每个 b权重减一 (-1)，然后，除了最后一个 b ，每个字母的所有单词的加法永远不能小于零。只有在单词的末尾添加才会是 -1 .如果这个词不满足这个条件，那么你可以认为它是无效的。