Finden Sie das kleinste Element größer als Daten, oder den Nachfolger (binäre Suchbaum)

Question

Ich habe eine BST-Klasse und BSTNode-Klasse, die beide vergleichbar. Ich muss das kleinste Element größer als Daten finden, oder den Nachfolger, aus der binäre Suchbaum. Ich weiß, ich habe zwei Fälle

1: Der rechte Unterbaum ist nicht leer ist, dann Nachfolger ist der am weitesten links liegende Knoten der rechte Unterbaum

2: Der rechte Unterbaum leer ist, dann Nachfolger ist der niedrigste Vorfahre von der Knoten, der Daten enthält, dessen linkes Kind auch ein Vorfahre von Daten ist. Beispiel:

   73 
      /\ 
      34 90 
      /\ 
      32 40 

Wenn wir die nextLargest von 40 finden müssen, würden Sie 73.

public T nextLargest(T data) { 
     return helperNL(data, root); 
} 
    private T helperNL(T data, BSTNode<T> root) { 
     if (data == null) { 
      throw new IllegalArgumentException("You can't look for null data"); 
     } 
     if (root == null) { 
      return null; 
     } 
     if (root.getRight() != null) { 
       BSTNode<T> dummyNode = root.getRight(); 
       //getting the leftmost node 
       while (dummyNode.getLeft() != null) { 
        dummyNode = dummyNode.getLeft(); 
       } 
       return dummyNode.getData(); 
     } 
     return null; 
    } 

zurückkehren Dies ist der Code, den ich bis jetzt haben. Jede Hilfe wäre willkommen!

Answer 1

Gehen Sie einfach für grundlegende Inorder Traversal. Nehmen Sie eine statische Variable, um die Daten des gerade durchlaufenen Knotens zu speichern. Wenn es den Daten entspricht (von denen Sie den Nachfolger finden müssen), drucken Sie den aktuellen Knoten.