你可以根据预先订购的二进制序列/顺序绘制二叉树吗？

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's和b's 组成的单词都属于Lukasiewicz语言.但是可以对它们应用一些可显示的规则.

首先,b's 的数量必须正好a是加1 的数量.其次,如果每个a权重加1(1)并且每个b权重减去1(-1),那么,除了最后一个b,每个字母的所有单词的加法永远不能小于零.只有在这个词的结尾处才会增加-1.如果单词不满足这个条件,那么你可以认为它是无效的.