Kleinstes Element im Baum, das größer ist als x

Question

Wenn ich das kleinste Element in einem Baum finden möchte, das größer als ein Element x ist, wäre das ein richtiger Weg?

class Node { 
    int data; 
    Node left, right; 
} 

Node root; 

public Integer successorOf(int x) { 
    return successorOf(x, root); 
} 

private Integer successorOf(int x, Node n) { 
    if (n == null) { 
     return null; 
    } 
    if (x < n.data) { 
     Integer res = successorOf(x, n.left); 
     if (res == null) 
      res = n.data; 
     return res; 
    } else { 
     return successorOf(x, n.right); 
    } 
} 

Ich fühle mich wie diese Lösung nicht den gesamten Baum überprüfen.

Hilfe wird sehr geschätzt!

Answer 1

Es ist nicht wahr, dass, wenn der Wert nicht auf der linken Seite war, es auf der rechten Seite ist. Vielleicht ist der Vater selbst der Richtige. Denke an einen Vater mit Daten = 6, sein linker Sohn Daten = 4, während sein rechter Daten = 10 hat. SuccessorOf (5) sollte den Vater zurückgeben.

private Integer successorOf(int x, Node n) { 
    if(n==null) 
     return null; 
    if(x < node.data){ 
    if(node.left!= null and node.left.data > x) 
     return successorOf(x, node.left); 
    else      
     return node.data; 
    } 
    else    //x >= n.data 
     return successorOf(x, node.right); 

Answer 2

Sie Inorder Traversal verwenden können, um die Elemente in aufsteigender Reihenfolge zu bekommen, und wenn Sie ein Element größer ist als die gewünschte dann finden Sie die Antwort

private int answer = -1;   // to store the answer 

traverse(root,x,0)    // call this method 

public void traverse(Node n,int x,int flag){ 

    if(n == null || flag == 1){ // flag=1 meaning we already found the answer 
     return; 
    } 
    traverse(n.left,x,flag); 
    if(n.data>x){     // smallest value greater than x 
     answer=n.data;   // store the answer 
     flag = 1;     // mark flag = 1, to make subsequent calls 
    }        // return from the function 
    traverse(n.right,x,flag); 

}