Wie Tiefe in einer Liste descrip einen binären Baum

Question

Zum Beispiel finden:

[[7, 0, 0], [2, 10, 11], [4, 9, 0], [6, 0, 0], [1, 8, 12], [9, 0, 2], [13, 0, 6], [5, 4, 3], [12, 0, 0], [10, 0, 0], [11, 0, 0], [3, 1, 13], [8, 7, 0]] Root=5

Eine Liste enthalten eine Unterliste, dass der erste Wert der Knoten und der zweite Wert ist, Kinder auf der linken Seite und die dritte ist die Kinder rechts. 0 bedeutet keine Kinder links/rechts, ich möchte die Tiefe jedes Knotens finden und Knoten in der gleichen Tiefe extrahieren.

p = lable.index(r)  
depth_list = []  
depth = 0  
depth_list.append([r, 0])  
while lable_left_right[p][1] != 0 or lable_left_right[p][2] != 0:  
    depth += 1  
    left = lable_left_right[p][1]  
    right = lable_left_right[p][2] 
    if left == 0 and right != 0:  
     p = right  
     depth_list.append([p, depth]) 
     continue 
    if right == 0 and left != 0: 
     p = left 
     depth_list.append([p, depth]) 
     continue 
    if left != 0 and right != 0: 
     p = right 
     depth_list.append([p, depth]) 
     p = left 
     depth_list.append([p, depth])  
     continue 

die lable ist eine Liste aller Knoten (in diesem Fall [7,2,4,6,1,9,13,5,12,10,11,3,8] und r ist die Wurzel. lable_left_right ist die gegebene Liste
ich bin stecken, wenn der Knoten zwei Kinder hat, aber ich kann nur nutzen eine p, um die While-Schleife fortzusetzen, so dass ich einen weiteren Kinder als Knoten verlieren, um die Aufgabe zu beenden.Es ist möglich, dass in der Mitte einer While-Schleife eine andere while-Schleife zu starten und die ursprüngliche Schleife weiterverarbeiten? Gibt es eine andere Möglichkeit, um die Tiefe aller Knoten zu erhalten?

Answer 1

Diese c Ein rekursiv gelöst werden mit Hilfe der folgenden:

tree = [[7, 0, 0], [2, 10, 11], [4, 9, 0], [6, 0, 0], [1, 8, 12], [9, 0, 2], [13, 0, 6], [5, 4, 3], [12, 0, 0], [10, 0, 0], [11, 0, 0], [3, 1, 13], [8, 7, 0]] 

def getRootNode(): 
    centernodes, leftnodes, rightnodes = map(list, zip(*tree)) 
    for node in centernodes: 
     if (node not in leftnodes) and (node not in rightnodes): 
      return node 

def getLeftNode(n): 
    for i in range(len(tree)): 
     if tree[i][0] == n: 
      return tree[i][1] 

def getRightNode(n): 
    for i in range(len(tree)): 
     if tree[i][0] == n: 
      return tree[i][2] 

def maxDepth(n): 
    if n == 0: 
     return 0 
    else: 
     lDepth = maxDepth(getLeftNode(n)) 
     rDepth = maxDepth(getRightNode(n)) 
     if (lDepth > rDepth): 
      return lDepth+1 
     else: 
      return rDepth+1 

n = getRootNode() 
print("Root Node is " + str(n)) 
depth = maxDepth(n) - 1 
print("Max Depth is " + str(depth))