3

(Python 2.7) 指定された preorder と inorder および preorder と inorder の文字列の最大長でバイナリ ツリーの 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

基本的に問題は、指定された preorder と inorder からツリーのすべてのparent-leftChildペアとparent-rightChildペアを取得する方法だと思います

親と左の子のペアを取得するには、次のことを確認する必要があります。2) ノード 2 が順番にノード 1 の前にある場合

あなたの例では preorder:ABCDE inorder:CBDAE

  • B は予約順序で A の直後にあり、B は順序で A の前にあるため、B は A の左側の子です。

  • D はプレオーダーでは C の直後ですが、D はインオーダーでも C の後にあるため、D は C の左側の子ではありません。

同様のトリックを使用して、すべての親と右の子のペアを取得できます

于 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 に答える