Erstellen Sie einen leeren Binärbaum in Python

Question

Ich bin ein Anfänger in der Programmierung, und ich konnte die Antwort in anderen Fragen nicht finden. Ich möchte einen leeren Binärbaum der Höhe h erstellen.

Mein Code:

class node: 
    def __init__(self, a = None): 
     self.value = a 
     self.left = None 
     self.right = None 

def postorder(tree,abba): 
    if tree != None: 
     postorder(tree.left,abba) 
     postorder(tree.right,abba) 
     abba.append(tree.value) 

def inorder(tree,abba): 
    if tree != None: 
     inorder(tree.left,abba) 
     abba.append(tree.value) 
     inorder(tree.right,abba) 

Ich mag wäre eine Funktion

def getBinaryTree(h): 

definieren, die mir einen Baum mit Niveau h ergibt. Also: empty tree of level

Irgendwelche Ideen?

Answer 1

Aktualisiert

Um einen binären Baum mit Höhe machen h, müssen Sie 2^(h+1)-1 Knoten hinzuzufügen. Ein Baum mit der Höhe 0 bedeutet, der Baum enthält nur einen Knoten und das ist der Stamm. Um beispielsweise einen Baum mit der Höhe 3 zu erstellen, müssen Sie 2^(3+1)-1 = 15 Knoten hinzufügen.

Wenn Sie eine Gruppe von Knoten erstellen möchten, die mit Ihrem gegebenen Code einen Binärbaum bilden können, können Sie so etwas tun.

import math 

class node: 
    def __init__(self, a = None): 
     self.value = a 
     self.left = None 
     self.right = None 

def getBinaryTree(tree_height): 
    tree_nodes = [None] * int((math.pow(2, tree_height+1) - 1)) 
    for i in range(tree_height): 
     start_index = int(math.pow(2, i) - 1) 
     end_index = int(math.pow(2, i+1) - 1) 
     for j in range(start_index, end_index): 
      tree_nodes[j] = node(j) 
      if j == 0: continue 
      if j % 2 == 0: # a right child 
       parent_index = int((j - 2)/2) 
       tree_nodes[parent_index].right = tree_nodes[j] 
      else: # a left child 
       parent_index = int((j - 1)/2) 
       tree_nodes[parent_index].left = tree_nodes[j] 

    return tree_nodes[0] # returns the root node 

def printTree(tree_node, inorder_tree_walk): 
    if tree_node != None: 
     printTree(tree_node.left, print_tree) 
     inorder_tree_walk.append(tree_node.value) 
     printTree(tree_node.right, print_tree) 

root = getBinaryTree(4) 
inorder_tree_walk = [] 
printTree(root, inorder_tree_walk) 
print(inorder_tree_walk) 

Also, was das Programm macht?

Das Programm erstellt 2^(h+1)-1 Knoten, um einen Baum mit der Höhe h zu bilden. Knoten werden in der Liste tree_nodes gespeichert. Die Eltern-Kind-Beziehung zwischen den Knoten wird wie folgt in tree_nodes gespeichert.

• Links Kind Element i: (2i + 1) -te Element
• Rechte Kind Element i: (2i + 2) -te Element

Wenn ein Kind-Knoten erstellt wird, ist es Legen Sie als Kinder links/rechts des Elternteils fest.