给定它的预序二进制 sequence/ordering，你能画出一棵二叉树吗？

Question

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

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

反过来也可以吗？如果给我这个二叉序列11011000101101010001，我能画出二叉树吗？

Answer 1

当然可以！

创建一棵二叉树，为每个元素分配一个数字

        0
   1----|-----2
 3-|-4     5--|--6
7|8 9|10 11|12 13|14
...

这些是你的指数。

定义节点数据的大小，您可以在 data_size * index

处获取树中节点的信息

这通常是堆的表示方式。

有很多方法可以将二叉树表示为字符串。但是，由于有很多方法，您必须先就特定表示达成一致，然后才能继续前进。我上面提到的只是表示二叉树的一种方式，它可能不是你们都使用的标准。

Answer 2

是的，你可以。

将内部节点标记为a，将外部节点标记为b；当然，您可以假设 a 为 0，b 为 1（反之亦然）。不过我觉得字母比数字更容易区分（虽然这事"taste"）。

如果你不知道"external nodes"是什么，那么你可以假设它们是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。如果这个词不满足这个条件，那么你可以认为它是无效的。

给定它的预序二进制 sequence/ordering，你能画出一棵二叉树吗？

Can you draw a binary tree given its pre-order binary sequence/ordering?

data-structures

binary-tree

huffman-code