Dynamische Variable Benennung für Baum [Python]

Question

Ich habe eine Baumstruktur für Preorder Traversal gemacht. Und ich kann alle Variablen manuell benennen.

Gibt es eine Möglichkeit, eine Variable zu erstellen. Ich brauche eine Baumstruktur wie folgt:

 0 
    1  2 
3 4  5 6 
7 8 9 10 11 12 13 14 
... 

und so weiter.

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

def fetch(root): 
    if root is None: 
     return 
    x = [] 
    x.append(root) 
    while(len(x) > 0):  
     node = x.pop() 
     print (node.data) 
     if node.right is not None: 
      x.append(node.right) 
     if node.left is not None: 
      x.append(node.left) 

root = Node(0) 

root.left = Node(1) 
root.right = Node(2) 
root.left.left = Node(3) 
root.left.right = Node(4) 
root.right.left = Node(5) 
root.right.right =Node(6) 
root.left.left.left=Node(7) 
root.left.left.right=Node(8) 

start_time=time.time() 
fetch(root) 
end_time=time.time() 

print ("Object time :"+str(end_time-start_time)) 

Ich möchte 1M Knoten haben. Was nicht manuell eingegeben werden kann. Könnte jemand bitte eine Funktion oder einen Weg vorschlagen? Danke!

Answer 1

Es scheint, dass Sie von links nach rechts auf dem Baum gehen. Wenn wir den Pfad binär darstellen, wird der am weitesten links liegende Zweig (auf der vierten Ebene nach unten) als 0000 (.left.left.left.left) dann die nächste Nummer 0001 (.left.left.left.right) sein. Dann wäre es 0010 (.left.left.right.left). Dies könnte wie folgt implementiert werden:

root = Node(0) 
level = 1 
branch = 0 
for n in range(1, 1000001): 
    *current_branch, final = '{:0{}b}'.format(branch, level) 
    # Makes current_branch the binary equivalent of <branch> 
    # padded with '0's to be <level> length 
    # and final is the last digit 
    place = root 
    for direction in current_branch: # Iteratively gets the correct path down the tree 
     # direction = ('left', 'right')[int(direction)] # '0' -> 'left;' '1' -> 'right' 
     place = getattr(place, ('left', 'right')[int(direction)]) 
    setattr(place, final, Node(n)) # Sets the final direction to the right Node 
    branch += 1 
    if branch >= 2 ** level: # If the branch is to the right of the right-most branch 
     branch = 0 
     level += 1 # Reset the branch and go a level deeper