レベルオーダートラバーサル - ツリー

Question

ツリーを出力として受け取るlevel_order_travelという関数を定義する必要があります。リスト内のすべてのノードのリストをレベル順に出力します。

ここで、次のコードはこれを示しています

def create_tree(node_list, index=1): 
    if index >= len(node_list) or node_list[index] is None: 
     return None 
    d = node_list[index] 
    l = index * 2 
    r = l + 1 
    tree = BinaryTree(d) 
    tree.set_left(create_tree(node_list, l)) 
    tree.set_right(create_tree(node_list, r)) 
    return tree 

def level_order_travel(a): 
### 

def test(): 
    list_of_leaves = [None, 10, 5, 15, None, None, 11, 22] 
    my_tree = create_tree(list_of_leaves) 

    print("Breadth first =", level_order_travel(my_tree)) 

test() 

これは私のBinaryTreeクラスです：

class BinaryTree: 

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

    def get_left(self): 
     return self.left 

    def get_right(self): 
     return self.right 

    def set_left(self, tree): 
     self.left = tree 

    def set_right(self, tree): 
     self.right = tree 

    def set_data(self, data): 
     self.data = data 

    def get_data(self): 
     return self.data 

    def create_string(self, spaces): 
     info = ' ' * spaces + str(self.data) 
     if self.left != None: 
      info += '\n(l)' + self.left.create_string(spaces+4) 
     if not self.right == None: 
      info += '\n(r)' + self.right.create_string(spaces+4) 
     return info  

    def __str__(self): 
     representation = self.create_string(0) 
     return representation 

これは私のキュークラスです：

class Queue: 
    def __init__(self): 
     self.items = [] 

    def is_empty(self): 
     return self.items == [] 

    def enqueue(self, item): 
     self.items.insert(0,item) 

    def dequeue(self): 
     return self.items.pop() 

    def size(self): 
     return len(self.items) 

    def peek(self): 
     return self.items[self.size() - 1] 

これは、これまでの私の試みです：

このは、次のような出力を生成する必要があります

[10, 5, 15, 11, 22] 

を代わりに、それは次の出力を生成します。

[10, 5, 15] 

すべてのヘルプは大歓迎です。ありがとうございました。

Answer 1

visitedノードを追跡するためにあなたのbfsトラバーサル機能を変更し、それは任意のグラフ（ツリーなどの非環式のものだけではなく）のために働くべきでは：

def breadth_first_traversal(a): 
    if a is None: 
     return [] 
    visited = set([]) 
    q = Queue() 
    q.enqueue(a) 
    list_of_leaves = [] 
    while not q.is_empty(): 
     a = q.dequeue() 
     visited.add(a)  
     child = a.get_left() 
     if child is not None and not child in visited: 
      q.enqueue(child) 
     child = a.get_right() 
     if child is not None and not child in visited: 
      q.enqueue(child) 
     list_of_leaves.append(a.get_data()) 
    return list_of_leaves 

test() 
# ('Breadth first =', [10, 5, 15, 11, 22]) 

また、あなただけの実装を使用したい場合tree秒間、あなたはさらに（各ノードは、各ノードは一つだけの親を持っているため、一度だけ訪問されることが保証されているので、あなたが、visitedノードを追跡する必要はありません）単純化することができます。

def breadth_first_traversal(a): # only for trees 
    if a is None: 
     return [] 
    q = Queue() 
    q.enqueue(a) 
    list_of_leaves = [] 
    while not q.is_empty(): 
     a = q.dequeue() 
     child = a.get_left() 
     if child is not None: 
      q.enqueue(child) 
     child = a.get_right() 
     if child is not None: 
      q.enqueue(child) 
     list_of_leaves.append(a.get_data()) 
    return list_of_leaves