python – 有多少种可能的数字组合构成相同的二叉树

发布时间：2020-12-20 13:47:38 所属栏目：Python 来源：网络整理

导读：建立：我有一个代表二叉树的数字列表.第一个数字的处理方式与其他数字不同,它是根.在数字的“其余”中,有些将高于根,有些将更低.命令较高的数字向左移动,而较年轻的数字则命令向右移动.例： list = [5,7,6,8,9,2,1,3,4]root = 5higher = [7,9] #in order of

建立：

我有一个代表二叉树的数字列表.第一个数字的处理方式与其他数字不同,它是根.在数字的“其余”中,有些将高于根,有些将更低.命令较高的数字向左移动,而较年轻的数字则命令向右移动.例：

list = [5,7,6,8,9,2,1,3,4]
root = 5
higher = [7,9] #in order of appearance
    root = 7
    higher = [8,9]
    lower  = [6]
lower  = [2,4] #in order of appearance
    root = 2
    higher = [3,4]
    lower  = [1]

在这种情况下,树看起来像这样：

5
                        -------------| |--------------
                       |                             |
                       7                             2
             8--------| |-------6             3-----| |-----1
         ---|                              ---|
        9                                 4

我希望找到一种方法来模拟可以安排列表[5,4]的可能组合的数量,以便制作相同的二叉树.解决方案绝对是递归的,因为在“更高”和“更低”数字列表中,它们可以进一步细分.

弄清楚所有数字的排列方式可以通过按照上面的列表分解树来开始.

父母可以混合,孩子可以混合,但孩子和父母不能混在一起

higher = [7,9]

但更高的列表不需要保持其[7,9]的顺序.只有那些不是另一棵树的父母的根以上的项目需要按照出现的顺序保存.由于6和8都是7的孩子,它们是可以互换的,但9必须在8之前,因为它是它的孩子.所以基本上重新排列此列表的唯一规则是：

>必须从7开始
> 8必须始终在9之前

因此,有三种组合.

[7,9]
[7,6]

所有这些都可以分解为相同的子树,因此我们的条件得到满足,现在我们可以查看低于主根的元素列表.

lower = [2,4]

下面的列表也不需要保留它的顺序,它遵循类似的规则,可以用三种不同的方式来编写相同的树：

[2,4]
[2,4,1]

我们现在有这个信息：
? – 较低的可以写3种方式
? – 可以用3种方式写出更高的值

有多少种不同的方法可以组合生成同一棵树？这是3 ^ 3吗？或者更多？

看看我知道的数字：

list = [5,4]

如果我列出可以在每个地点进行的可能数字列表,这里是我最终获得的数量：

列表的第一个元素必须是5,它是根.之后它必须是2或7,因为其他任何东西都会打破更高/更低列表的顺序.在那之后,它会变得混乱.

如果第二个数字= 2,则第三个数字可以是三个事物之一,3或7.

如果第二个数字= 7,则第三个数字可以是三个事物中的一个,即6,8或2.

在此之后,它扩大得更大,组合变得非常快.我的问题是,有没有办法以有效的方式递归检索总可能组合的数量？我将在python中执行此操作.谢谢.

解决方法

建立在上面的想法….这是python生成器代码,以产生所有等效的排序.

import collections

Node = collections.namedtuple('Node',('root','left','right'))

def tree_from_list(lst):
    if not lst:
        return None
    root = lst[0]
    left_lst = [x for x in lst if x > root]
    right_lst = [x for x in lst if x < root]
    return Node(root,tree_from_list(left_lst),tree_from_list(right_lst))

def parent(key,tree):
    if tree is None:
        return -1
    elif (tree.left != None) and (tree.left.root == key): 
        return tree.root
    elif (tree.right != None) and  (tree.right.root == key):
        return tree.root
    elif (key > tree.root):
        return parent(key,tree.left)
    else: return parent(key,tree.right)

def all_insert_after(key,target,seq):
    i = seq.index(key)
    for j in range(i,len(seq)):
            mylist =  seq[:j+1] + [target] + seq[j+1:]
            yield mylist

def all_equivalent_orderings(seq):
    if (len(seq)==1):
    yield seq
    else:
        z = seq[-1]
        p = parent(z,tree_from_list(seq))
        for a in all_equivalent_orderings(seq[:-1]):    
            for b in all_insert_after(p,z,a):
                yield b  

print "Here are all 630 equivalent orderings of [5,4]"         
for o in all_equivalent_orderings([5,4]):
    print o

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!