从Python列表中创建二进制树

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

导读：我需要从列表列表中创建二叉树.我的问题是一些节点重叠(在一个意义上,一个节点的左边是另一个节点的右边),我想将它们分开. 我复制了重叠的节点并创建了一个列表,但我遗漏了一些东西.我用来做的代码： self.root = root = BNodeItem(values[0][0],0)q = list(

我需要从列表列表中创建二叉树.我的问题是一些节点重叠(在一个意义上,一个节点的左边是另一个节点的右边),我想将它们分开.

我复制了重叠的节点并创建了一个列表,但我遗漏了一些东西.我用来做的代码：

self.root = root = BNodeItem(values[0][0],0)
q = list()
q.append(root)

# make single tree list
tree_list = list()
tree_list.append(values[0][0])
for i in xrange(1,len(values[0])):
    ll = [i for i in numpy.array(values)[:,i] if i is not None]
    # duplicate the values
    p = []
    for item in ll[1:-1]:
        p.append(item)
        p.append(item)
    new_ll = list()
    new_ll.append(ll[0])
    new_ll.extend(p)
    new_ll.append(ll[-1])
    tree_list.extend(new_ll)
# fix tree
for ind in xrange(len(tree_list)/2 - 1):
    eval_node = q.pop(0)
    eval_node.left = BNodeItem(tree_list[2*ind + 1],0)
    eval_node.right = BNodeItem(tree_list[2*ind + 2],0)
    q.append(eval_node.left)
    q.append(eval_node.right)

“values”变量看起来像这样(其中0我通常没有)：

100   141.9068   201.3753   285.7651    405.5200    575.4603
0     70.4688    100        141.9068    201.3753    285.7651
0     0          49.6585    70.4688     100.0000    141.9068
0     0          0          34.9938     49.6585     70.4688
0     0          0          0           24.6597     34.9938
0     0          0          0           0           17.3774

因此,例如,行中的141.9 = 1具有子行为201.3和行中的100 = 2,但是70.4在行2中具有子100和49.6(共享100).

有什么建议？

编辑：在len()和从列表值(错误列表)创建节点时出错.好像还有一个bug.

似乎它正在发挥作用

使用它来打印@Arthur的解决方案中的树：

class Node():
    def __init__(self,value):
        self.value = value

        self.leftChild = None
        self.rightChild= None
    def __str__(self,depth=0):
        ret = ""
        if self.leftChild is not None:
            ret += self.leftChild.__str__(depth + 1)
        ret += "n" + ("                                     " * depth) + str(self.value)
        if self.rightChild is not None:
            ret += self.rightChild.__str__(depth + 1)
        return ret

解决方法

这里有一个解决方案,它返回一个具有左右子节点的Node对象,允许您使用大多数树解析算法.如果需要,您可以轻松添加对父节点的引用.

data2 = [[1,2,3],[0,4,5],6]]

def exceptFirstColumn(data):
    if data and data[0] :
        return [ row[1:] for row in data ]
    else :
        return []

def exceptFirstLine(data):
    if data :
        return data[1:]

def left(data):
    """ Returns the part of the data use to build the left subTree """
    return exceptFirstColumn(data)

def right(data):
    """ Returns the part of the data used to build the right subtree """
    return exceptFirstColumn(exceptFirstLine(data))
class Node():
    def __init__(self,value):
        self.value = value

        self.leftChild = None
        self.rightChild= None

    def __repr__(self):
        if self.leftChild != None and self.rightChild != None :
            return "[{0} (L:{1} | R:{2}]".format(self.value,self.leftChild.__repr__(),self.rightChild.__repr__())
        else:
            return "[{0}]".format(self.value)

def fromData2Tree(data):    
    if data and data[0] :
        node = Node(data[0][0])

        node.leftChild = fromData2Tree(left(data))
        node.rightChild= fromData2Tree(right(data))

        return node

    else :
        return None

tree = fromData2Tree(data2)
print(tree)

此代码提供以下结果：

[1 (L:[2 (L:[3] | R:[5]] | R:[4 (L:[5] | R:[6]]]

这是请求的后续树.测试你的数据,它的工作原理.现在尝试了解它是如何工作的;)

+-----1-----+
   |           |
+--2--+     +--4--+
|     |     |     |
3     5     5     6

（编辑：李大同）

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