python中来自preorder和inord的BFS

Question

（Python2.7）我需要用给定的preorder和inorder以及preorder和inorder字符串的最大长度来打印二叉树的bfs。 我知道它的工作原理，例如： 预购：ABCDE 顺序：CBDAE 最大值长度：5在

                A
             /     \
           B        E
          / \         
         C   D

在BFS：ABECD在

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

^{pr2}$

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

Answer 1

如果您使用的是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

Answer 2

我想问题的实质是如何从给定的前序和序中得到树的所有父leftChild对和parent rightChild对

要获得父leftChild对，需要检查：1）node1是否在preorder中node2之后；2）node2是否在inorder的node1前面

以你为例预订单：ABCDE inorder：中央商务区

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

• D在前序中位于C之后，而D在序中也在C之后，因此D不是C的左子级

您可以使用类似的技巧来获得所有的父子对

Answer 3

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