Level Order Traversal - Baum

Question

Ich muss eine Funktion namens level_order_travel definieren, die einen Baum als Ausgabe, a, nimmt und eine Liste aller Knoten in der Liste in der Ebenenreihenfolge druckt.

Der folgende Code hier zeigt dies:

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() 

Das ist mein BinaryTree Klasse:

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 

Das ist meine Klasse Queue:

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] 

Dies ist mein Versuch, so weit :

Dies sollte die folgende Ausgabe:

[10, 5, 15, 11, 22] 

sondern erzeugt es die folgende Ausgabe:

[10, 5, 15] 

Jede Hilfe sehr geschätzt wird. Vielen Dank.

Answer 1

Ändern Sie bitte Ihre bfs Traversal-Funktion Spur der visited Knoten zu halten, sollte es für jeden Graphen arbeiten (nicht nur die azyklische diejenigen als Bäume):

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]) 

Auch, wenn Sie die Implementierung verwenden möchten nur für tree s dann können Sie weiter zu vereinfachen (Sie brauchen nicht den Überblick über die visited Knoten zu halten, da jeder Knoten nur einmal besucht werden sollen, ist garantiert für jeden Knoten hat nur ein Elternteil):

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