代表免费树到二叉树

这个练习是从书"algorithms in c++"。假设有这样一棵免费树代表免费树到二叉树

第一个问题：我们能否将这个自由树表示为二叉树？

我认为我们不能将这个自由树表示为二叉树，因为有一些节点有两个以上的子节点。

第二个问题：我们可以用这棵免费树表示多少有序树？

我不明白这个问题。节点中没有键来决定如何创建一个有序的树。

2016-12-25 Dimitris Dimitriadis

可以代表具有任意数量的每个子节点为[左孩子右兄弟二叉树]树（https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree）。因此，有多于两个孩子的节点的存在不是拒绝二叉树作为你的自由树的表示的理由。 –

我相信第二个问题是问自己从自由树开始可以创建多少棵不同的树，然后向边添加一个方向性，使得生成的树是一棵定向的根树。 – templatetypedef

非常感谢您的回答。我不知道左子右兄弟二叉树。对于第二个问题，我必须创建有序树而不是无序树（根树）。 –

如果我正确地理解了这个问题，那么任务就是将树表示为二叉树，即使用二叉树的数据结构来表示任意树。从结构上讲，这个问题需要一种将任意树映射到二叉树的方法。

该技术被描述为here;基本思想是通过任意选择的子女来代表节点a的子节点c_1,...c_n，子节点a可以是两个以上，该子节点成为a的左子节点。作为c_1的右边孩子，下一个孩子c_2被存储;等等。这意味着对于每个节点，一个孩子存储在左侧子树中，而在右侧子树中通过总是选择正确的孩子，存储孩子的“替代方案”的“兄弟姐妹”。该方法可以描绘如下。请忍受我的相对较差的文字表示。

arbitrary tree 

     a 
/| | \ 
c_1 c_2 c_3 c-4 

binary tree 

    a 
/
c_1 
    \ 
    c_2 
     \ 
     c_3 
      \ 
      c_4

来源

2016-12-25 21:35:36 Codor

谢谢你的回答。 –

代表免费树到二叉树

回答

相关问题