Python-Liste von Python-Binärbaum

Question

Ich möchte eine Funktion definieren, die eine Liste der Tree-Knoten-Werte zurückgibt. Die Liste befindet sich in der Reihenfolge der Ebenen (von oben nach unten, von links nach rechts).

Zum Beispiel kann die Liste von oben wäre gezeigt Baum hergestellt: [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None, end].

Dies ist die Implementierung Binary Tree ist

class BinaryTree: 

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

    def insert(self, data): 
     node = self 
     while node is not None: 
      parent = node 
      if node.left is None: 
       parent.insert_left(data) 
       break 
      if node.right is None: 
       parent.insert_right(data) 
       break 
      node = node.left 

    def insert_left(self, data): 
     self.left = BinaryTree(data, left=self.left) 

    def insert_right(self, data): 
     self.right = BinaryTree(data, right=self.right) 

    def get_left_subtree(self): 
     return self.left 

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

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

    def get_right_subtree(self): 
     return self.right 

    def set_value(self, val): 
     self.key = val 

    def get_value(self): 
     return self.key 

    def create_string(self, indent): 
     string = str(self.key) + '---+' 
     if self.left: 
      string += '\n(l)' + indent + self.left.create_string(indent + ' ') 
     if self.right: 
      string += '\n(r)' + indent + self.right.create_string(indent + ' ') 
     return string 

    def __str__(self): 
     return self.create_string(' ') 

Answer 1

Für Level-Order Traversal, ein iterativer Algorithmus ist die natürlichste, zum Beispiel:

def create_list(tree, templist=[]): 
    """ 
    >>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9)))) 
    >>> create_list(tree) 
    [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None] 

    """ 
    items = [] 
    queue = [tree] 

    while queue: 
     copy = queue[:] 
     queue = [] 

     for item in copy: 
      if item is None: 
       items.append(None) 
       queue.append(None) 
       queue.append(None) 
      else: 
       items.append(item.key) 
       queue.append(item.left) 
       queue.append(item.right) 

     if all((x is None for x in queue)): 
      break 

    return items 

Wenn Sie wirklich wirklich eine rekursive Implementierung wirklich wollen:

def create_list_rec(tree, items=[], queue=[]): 
    """ 
    >>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9)))) 
    >>> create_list_rec(tree) 
    [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None] 

    """ 
    if not items and not queue: 
     return create_list_rec(None, [], [tree]) 

    copy = queue[:] 
    queue = [] 

    for item in copy: 
     if item is None: 
      items.append(None) 
      queue.append(None) 
      queue.append(None) 
     else: 
      items.append(item.key) 
      queue.append(item.left) 
      queue.append(item.right) 

    if all((x is None for x in queue)): 
     return items 

    return create_list_rec(items, queue) 

Answer 2

viele Implementierungen von Baumklassen auf GitHub Es gibt keine.

Hier ist ein gutes Beispiel, das Sie aus arbeiten könnten:

https://github.com/Yash3667/BinaryTree