3

（Python 2.7）我需要打印具有给定预序和中序的二叉树的 bfs，以及预序和中序字符串的最大长度。我知道它是如何工作的，例如：preorder:ABCDE inorder:CBDAE max length:5

                A
             /     \
           B        E
          / \         
         C   D

BFS:ABECD

到目前为止，我已经弄清楚了

class BinaryTree:
    def __init__ (self, value, parent=None):
            self.parent = parent
            self.left_child = None
            self.right_child = None
            self.value=value

    def setLeftChild(self, child=None):
            self.left_child = child
            if child:
                child.parent = self

    def setRightChild(self, child=None):
            self.right_child = child
            if child:
                child.parent = self


preorder={}
inorder={}

print "max string length?"
i=int(raw_input())
count=0
while i>count:
    print"insert the preorder"
    preorder[raw_input()]=count
    count=count+1
print "preorder is",sorted(preorder, key=preorder.get)

count2=0
while i>count2:
    print"insert the inorder"
    inorder[raw_input()]=count2
    count2=count2+1
print "inorder is",sorted(inorder, key=inorder.get)
root=

我已经想出了如何在 python 中创建二叉树，但问题是我不知道如何添加下一个孩子的值。如您所见，我已经有了根并想出了如何插入第一个孩子（左和右），但我不知道如何添加下一个。

4

3 回答 3

2

我想基本上问题是如何从给定的前序和有序中获取树的所有父-左子对和父-右子对

要获得 parent-leftChild 对，您需要检查： 1) node1 在前序中是否在 node2 之后；2）如果node2按顺序在node1前面

对于您的示例预购：ABCDE 中序：CBDAE

  • B在前序中在A之后，B在前序中在A之前，因此B是A的左孩子。

  • D在前序中紧跟在C之后，但在顺序上D也在C之后，因此D不是C的左孩子

您可以使用类似的技巧来获取所有 parent-rightChild 对

于 2012-06-24T05:07:02.897 回答
1

要将子节点添加到任何节点，只需获取要添加子节点的节点并在其上调用 setLeftChild 或 setRightChild。

于 2012-06-24T04:48:53.190 回答
0

如果您使用 BFS - 理想情况下希望使用图形 - 一个优秀的库是networkx

一个例子：

import networkx as nx

g = nx.DiGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'E')
g.add_edge('B', 'C')
g.add_edge('B', 'D')

print 'A' + ''.join(node[1] for node in (nx.bfs_edges(g, 'A')))

# ABECD
于 2012-06-24T05:40:58.093 回答