ループを介してバイナリツリーを作成する

Question

ループを反復してバイナリツリーを作成します。私は非常に基本的なバイナリツリーを書く方法を知っています。

class Tree(object): 
    def __init__(self): 
     self.left = None 
     self.right = None 
     self.data = None 


root = Tree() 
root.data = 75 
root.left = Tree() 
root.left.data = 95 
root.right = Tree() 
root.right.data = 64 

root.left.left = Tree() 
root.left.left.data = 32 
root.left.right = Tree() 
root.left.right.data = 93 
root.left.left = Tree() 
root.right.left.data = 32 
root.left.right = Tree() 
root.right.right.data = 93 

print(root.data) 

これをhandtyping退屈である、と私は番号のリストを持っていた場合：

list = [1,2,3,4,5,6,7] 

ので、この順番でバイナリツリーを作成するために、ループを通してそれを置く：

1 
2 3 
4 5 6 7 

どうすればいいですか？私はすべてのパスの合計を計算するためにこれを使用していますのでと、どのようにバイナリツリーを反復処理/ナビゲートします：

Answer 1

フルバイナリツリー（必ずしも二分探索木）からをビルドするにはノード値のリストは、リスト内の値がレベルオーダートラバーサルに従って並べられていると仮定します。だから、あなたの質問からリスト

values = [1,2,3,4,5,6,7] 

は木を表現します：ルート値が位置0で、その左の子が位置1*2-1=1であるされていることを

1 
2 3 
4 5 6 7 

お知らせ、の右の子を1*2=2などである。一般に、インデックスiのリスト内のノードの左の子は位置(i+1)*2-1にあり、右の子は(i+1)*2にある。

ここでは、左と右のサブツリーを作成する各ステップで、ノードごとに再帰的にツリーを構築する必要があります。

簡略化するため、valuesのリストがグローバルであるとします。

class Node(object): 
    def __init__(self, data=None, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 

def buildTree(i): 
    if i < len(values): 
     return Node(values[i], left=buildTree((i+1)*2-1), right=buildTree((i+1)*2)) 

values = [1,2,3,4,5,6,7] 
tree = buildTree(0) 

プリントアウトするために木を、我々はpreorder tree traversalを使用することができます。

このよう

def preorder(node): 
    if node is None: 
     return 
    yield node.data 
    for v in preorder(node.left): 
     yield v 
    for v in preorder(node.right): 
     yield v 

：

>>> print list(preorder(tree)) 
[1, 2, 4, 5, 3, 6, 7] 

Answer 2

ここでは、あなたの質問以来、間に合わせのn-反復アプローチは、（ですループに言及しています！）は、リストとフラグを使用して、ちょうど挿入されたものと次に何が入る必要があるのか​​を追跡します。 ...私達の機能をテストし、

def createTree(values): 
    _root = Tree() 
    _root.data = values[0] 

    nodes = [_root] 
    direction = 0 # 0 => left, 1 => right 

    for val in values[1:]: 
     root = nodes.pop(0) # pop the first element, this is the one whose children we need to create 

     node = Tree() # create the next child 
     node.data = val 

     if direction == 0: # we've to attach to the the left child 
      direction = 1 # reverse the direction 
      root.left = node # attach the child 
      nodes.insert(0, root) # put root back, we need to attach to its right child for the next value 
      nodes.append(node) # place the left child at the end of the queue/stack 
     else: # attach to right child 
      direction = 0 # reverse direction 
      root.right = node # do the attachment 

      nodes.append(node) # same policy as left node 

    return _root # done, now return 

そして

root = createTree([1, 2, 3, 4, 5, 6, 7]) 

print(root.data) 
print(root.left.data) 
print(root.right.data) 
print(root.left.left.data) 
print(root.left.right.data) 
print(root.right.left.data) 
print(root.right.right.data) 

出力：コメントは、インライン化

1 
2 
3 
4 
5 
6 
7