P. Tengo preguntas sobre el recorrido del árbol de búsqueda binaria mediante la recursividad y el retorno. Tengo que tomar un BST con las teclas ordenadas en orden ascendente y "invertirlo" para que todas las teclas estén en orden descendente, como se puede ver en la imagen.

Según mi comprensión del código a continuación, creo que los pasos son:

  ->reverseKeys (10)  ->reverseKeys (2)
  ->reverseKeys (null): return 
  ->reversekeys(null): return 
  ->BSTNODE <T> ptr = root.left; 
  ->root.left = root.right;
  ->root.right = ptr;  

Creo que malinterpreté el código. ¿Alguien puede explicar cómo este código puede cambiar la imagen de la izquierda a la derecha? Apreciaría cualquier ayuda.

   25                 25 
  /  \               /  \ 
 10  40      --->   40   10 
 /\   /\           / \  / \ 
2 20 30 45        45 30 20  2 
 /    \              /   \
15    35            35   15 

 public static <T extends Comparable<T>> 
void reverseKeys(BSTNode<T> root) {
   if (root == null) { 
      return;
   }
   reverseKeys(root.left);
   reverseKeys(root.right);
   BSTNode<T> ptr = root.left;
   root.left = root.right;
   root.right = ptr;
}
-1
Rebecca L 11 nov. 2017 a las 21:51

2 respuestas

La mejor respuesta

Verifique el BST - Cruce de orden inverso (RVL) del siguiente código

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

// Search with a valid node returned, assuming int

public Node traverse (Node root, int data){ // What data are you looking for again?
    if(root.data == data) {
        return root;
    }
    if (root.left != null){
        return traverse (root.left, data);
    }
    if (root.right != null){
        return traverse (root.right, data);
    }
    return null;
}
0
ramana vv 11 nov. 2017 a las 19:05

Estas líneas simplemente intercambian los subárboles izquierdo y derecho por un nodo. Y debido a las llamadas recursivas al método, cada nodo tiene subárboles izquierdo y derecho intercambiados cuando se ejecuta el método.

BSTNode<T> ptr = root.left;
root.left = root.right;
root.right = ptr;
1
Ivan 11 nov. 2017 a las 19:31