Probleme mit dem nächsten Inorder-Knoten im binären Suchbaum haben

Question

Ich stecke auf dieses Problem fest. Der Randfall, bei dem ich versage, ist, wenn der gegebene Knoten (self) der größte Knoten im Baum ist. Ich würde mich über Hinweise zur Lösung des Problems freuen.

Die Fälle, die ich habe, sind wenn das Recht des Knotens None ist, dann weiß ich, dass die Lösung Großeltern oder None sein wird.

Ein weiterer Fall ist, wenn rechts nicht keine ist. In diesem Fall rufe ich das rechte Kind an und finde den Knoten ganz links, da dies der kleinste Knoten ist, der größer als der Start-Selbstknoten ist.

Geben Sie für ein BSTNode-Objekt den nächsten Knoten in der Reihenfolge zurück.

class BSTNode: 
    def __init__(self, left, right, parent): 
     self.left = left  # BSTNode 
     self.right = right  # BSTNode 
     self.parent = parent # BSTNode 


    def nextInorderNode(self): 

wenn Selbst 1, 3 zurückzukehren

war, wenn Selbst 3, 4 zurückzukehren

ist, wenn Selbst 4 ist, das Rück 5

wenn Selbst 9 ist, zurück Keine

meine Lösung:

class BSTNode: 
    def __init__(self, left, right, parent): 
     self.left = left  # BSTNode 
     self.right = right  # BSTNode 
     self.parent = parent # BSTNode 



def find_left_most(self): 
    if (self == None): 
     return self 
    next = self 
    while (next != None): 
     if (next.left == None): 
      return next 
     next = next.left 

def nextInorderNode(self): 

    if self.right == None: 
     parent = self.parent 
     if (parent.left == self): 
      return parent 

     else: 
      curr_node = parent.right 
      grand_parent = parent.parent 
      return grand_parent 

    else: 
     child = self.right 
     return child.find_left_most() 

Answer 1

Wenn Sie nextInorderNode umschreiben den Baum, bis der Suche nach einem Knoten, der self links von, ich glaube, das wird Ihnen das gewünschte Ergebnis zu Fuß bis:

def nextInorderNode(self): 
    if self.right is None: 
     curr_node = self 
     parent = curr_node.parent 
     while parent and parent.left != curr_node: 
      curr_node = parent 
      parent = curr_node.parent 
     return parent 

    child = self.right 
    return child.find_left_most()