BFS in python from preorder and in

（Python 2.7）我需要打印一个二叉树的bfs，包含一个给定的前序和inorder，以及一个最大长度的前序和inorder序列。我知道它是如何工作的，例如：序：ABCDE 序：CBDAE 最大长度：5BFS in python from preorder and in

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中创建一个二叉树，但事情是我不知道如何添加下一个孩子的值。正如你所看到的，我已经有了根，并想出了如何插入第一个孩子（左侧和右侧），但我不知道如何添加下一个孩子。

来源

2012-06-24 TomMe

要向任何节点添加子节点，只需获取要添加子节点的节点并调用setLeftChild或setRightChild就可以了。

来源

2012-06-24 04:48:53 Antimony

像root.left_child。 setLeftChild（BinaryTree（preorder [2]））？ – TomMe

我想主要问题是如何让所有的家长leftChild对，并从给定序树的家长rightChild对和序

为了让家长leftChild对，你需要检查：1 ）如果节点1在节点2之后正好在前序; 2）如果节点2是在节点1的前面在序

对于示例序：ABCDE中序：CBDAE

B是A之后在预订和B是在A的前面在序，从而乙是A的左子
d为序℃之后的权利，但d也是ç后序，因此d是也不是C

您可以使用类似的左子招让所有的家长rightChild对

来源

2012-06-24 05:07:02 xvatar

所以我应该做一个“如果”例如，以确定哪里的节点去基于前序和inorder输入我给了？事情是，前序和中序长度可以大于5，这就是我有点困惑。谢谢你的帮助。 – TomMe

@TomásMedina是的，你应该在序列表中得到像A-B，B-C，C-D ...这样的所有对，并在inorder列表中进行验证。所以，无论预购单的时间长短如何，无论如何你都需要经过 – xvatar

好吧，看起来我在正确的轨道上，但是对于获得所有配对，你的意思是什么？我不明白那一部分。我在考虑比较两个列表之间的元素位置，并从中决定他们去哪里。这是好的还是你认为有一个更简单或有效的方式来做到这一点？ – TomMe

如果你使用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-24 05:40:58

BFS in python from preorder and in

回答

相关问题