给定二进制序列/排序可以绘制二叉树？ [英] Can you draw a binary tree given its pre-order binary sequence/ordering?

问题描述

二进制树（因此有序的林）可以表示为二进制字符串。二进制字符串是通过以预订方式遍历一个二叉树，为每个节点记录一个，每个空子树记录一个0（空链接）。

这意味着如果我给了一个二叉树，我可以做一个preorder遍历，并产生二进制序列表示。

相反也可以吗？如果我给出这个二进制序列 11011000101101010001 ，我可以绘制二叉树吗？

解决方案<

将内部节点标记为 a ，将外部节点标记为 b ;当然，您可以将 a 作为 0 和 b 1 （反之亦然）。但是我认为比数字更容易区分字母（虽然这个味道这个问题）。

如果你不知道什么是外部节点，那么你可以假定它们是 NULL 指针。

现在，我按照我的说，形成一个属于卢卡西维茨语言的词。可以看出，这个词是独一无二的。也就是说，对于任何一对树 t1 和 t2 ，代码（t1）！=代码（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 。如果这个词不符合这个条件，那么你可以假定它是无效的。

Binary trees (and hence ordered forests) can be represented as binary strings. The binary string is obtained by traversing a binary tree in preorder, recording a 1 for every node and a 0 for every empty subtree (null link).

This means that if I'm given a binary tree, I can do a preorder traversal and produce a binary sequence representation.

Is the opposite also possible? If I'm given this binary sequence 11011000101101010001, can I draw the binary tree?

解决方案

Yes you can.

Label the internal nodes as a and the external ones as b; of course you can assume a as 0 and b as 1 (and vice-versa). But I think is easier to distinguish letters than numbers (although this matter of "taste").

If you don't know what are the "external nodes", then you can assume that they are the NULL pointers.

Now, the preorder traversal of any tree labeled as I have said forms a word belonging to Lukasiewicz language. It could be shown that this word is unique. That is, for any pair of trees t1 and t2, code(t1) != code(t2); always! In addition (and this should have been the reason for which you are concerned to Huffman encoding), the Lukasiewicz language is prefix.

For example, for the tree

Its preorder traversal is aaaabbabbaabbbababb or 000011011001110111

I leave to you the code for generating a code; it is a preorder traversal. If you are interested in reversing it, that is, to get the tree given the code, then this pseudo-code, which tries to answer your question, would do it:

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;
}

In a real implementation, you would read bits.

The routine above assumes that the code is right; that is, it was generated from a binary tree. Note that not all words composed by a's and b's belong to the Lukasiewicz language. But some showable rules could be applied on them.

First, the number of b's must be exactly the number of a's plus one. Second, if each a weights one (1) and each b weights minus one (-1), then, at the exception of last b, the addition through all the word for each letter never can be smaller than zero. Only at the end of the word the addition will be -1. If the word does not satisfy this condition, then you can assume that it is invalid.

这篇关于给定二进制序列/排序可以绘制二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！