用Python实现从先序遍历和中序遍历构建二叉树的算法

Question

（Python 2.7）我需要打印出给定先序和中序的二叉树的广度优先遍历，并且先序和中序字符串的最大长度已知。 我知道它是如何工作的，例如： 先序：ABCDE 中序：CBDAE 最大长度：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中创建二叉树，但是问题是我不知道如何添加下一个子节点的值。正如您所看到的，我已经有了根节点，并且学会了如何插入第一个子节点（左和右），但我不知道如何添加下一个子节点。

- TomMe

Answer 1

我想，问题的本质是如何从给定的前序遍历和中序遍历中获取树的所有父节点-左子节点对和父节点-右子节点对。

要获取父节点-左子节点对，您需要检查以下内容：1）如果node1在preorder中紧随node2后面；2）如果node2在inorder中在node1前面。

以您的示例preorder：ABCDE inorder：CBDAE为例：

- B在preorder中紧随A后面，在inorder中在A前面，因此B是A的左子节点。 - D在preorder中紧随C后面，但在inorder中也在C之后，因此D不是C的左子节点。

您可以使用类似的技巧来获取所有父节点-右子节点对。

- xvatar

---

那么我应该做一个“if”语句，根据我得到的前序遍历和中序遍历输入来确定节点的位置吗？问题在于前序遍历和中序遍历的长度可能大于5，这就让我有点困惑了。感谢您的帮助。 - TomMe

@TomásMedina 是的，你应该在 preorder 列表中获取所有的 A-B、B-C、C-D 等配对，并在 inorder 列表中验证它们。因此，preorder 列表有多长并不重要，你都需要遍历它。 - xvatar

好的，看起来我走在了正确的道路上，但你所说的获取所有配对是什么意思？我不理解这一部分。 我在考虑比较两个列表中元素的位置，并根据此确定它们的位置。这样可以吗？或者您认为有更简单或更有效的方法吗？ - TomMe

@TomásMedina 我的意思是在前序列表中对A和B进行检查，然后在中序列表中查看它们以确定B是否出现在A之前，如果是，则意味着B是A的左子节点。 对于预订单列表中的其他配对，如B和C、C和D、D和E，您也要进行相同的检查。 如果“pair”一词让您感到困惑，我很抱歉，但希望您能明白我的意思。 - xvatar

哦，那正是我想做的事情，看起来我们都在谈论同一件事情，只是方式不同。但现在我该如何比较这两个列表之间的位置呢？非常感谢你的帮助。 - TomMe

我刚刚编辑了代码，现在我正在使用字典，因为我发现它更容易使用，因为它已经为每个位置提供了值。 - TomMe

Answer 2

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

- Antimony

---

像 root.left_child.setLeftChild(BinaryTree(preorder[2])) 这样的编程内容？ - TomMe

Answer 3

如果您正在使用 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

- Jon Clements