tree - partir - ¿Cómo obtener la ruta desde la raíz a un nodo dado en un árbol binario?

ejemplos de arboles en python

Question

Estoy intentando descubrir cómo obtener la ruta desde la raíz a un nodo determinado en un árbol binario.

No es un árbol de búsqueda binario.

Cada nodo no hoja tiene solo dos punteros a sus hijos.

In-order, pre-order, post-order transversal no funcionan.

He intentado hacer pre-orden, pero no puedo averiguar cómo. Por ejemplo, tenemos un árbol binario: NO es un árbol de búsqueda binario. Usamos el nodo de orden de clasificación para que sea más fácil encontrar la ruta.

     1 
   /   /
  2     3
 / /   / /
4   5 6   7 

Queremos encontrar el camino del 1 al 7:

Con pre-pedido, tenemos:

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 

Desde el flujo, obtenemos la ruta de 1 -> 7 con todos los nodos en ella.

Obviamente, no debería ser.

Cualquier ayuda es muy apreciada.

Answer 1

Considere el siguiente árbol:

       10
     /   /
    8      2
  /  /    /
3     5  2

Enfoque

• Comenzamos desde la raíz y la comparamos con la clave, si coinciden, imprimimos la ruta (si el árbol tiene solo un nodo, la ruta solo contiene la raíz).
• De lo contrario, empuje el nodo en Vector (consideré el vector para almacenar la ruta).
• Recursivamente ir a la izquierda y derecha del árbol.

El siguiente código ayudará:

     void PrintPath(node* root, vector <int> v,int key)
     {
      if(!root)
      return;
      if(root->data==key)
        {
          v.push_back(root->data);
          vector<int>:: iterator it;
          for(it=v.begin();it<v.end();it++)
           {
             cout<<*it<<" ";
           }
            return;
        }
        v.push_back(root->data);
        PrintPath(root->left,v,key);
        PrintPath(root->right,v,key);
    }    

Explicación

Deje que el nodo que se encuentra sea 5 (clave) para el árbol dado.

Contenido del vector en cada paso:

1. V = 10
2. V = 10,8
3. V = 10,8,3 (3 no es la clave, por lo que retrocederemos e iremos a la derecha)
4. V = 10,8,5 (5 es la clave, por lo tanto, imprima la ruta).

Answer 2

El recorrido de preorden, también conocido como búsqueda en profundidad , funciona.

• Si implementa recursivamente el recorrido de la preorden, entonces cuando llegue al nodo deseado, puede desenrollar su pila (de llamadas recursivas) y construir su camino en sentido inverso.

• Si implementa el recorrido de la preorden de forma no recursiva, entonces estará construyendo una pila directamente, por lo que en este caso, una vez que llegue al nodo deseado, ya tendrá su ruta.

En el árbol en su pregunta anterior, el algoritmo para encontrar la ruta de 1 a 7 procede de la siguiente manera.

• Comienza con 1, empújalo en la pila, la pila es ahora [1]
• Ve a la izquierda a la 2, empújalo en la pila, la pila es ahora [1 2]
• Ve a la izquierda al 4, empújalo, la pila es ahora [1 2 4]
• No hay hijos de 4, y no es lo que quieres, así que, pop, stack is now [1 2]
• Ahora que has vuelto a la 2, y ya has ido a la izquierda, ahora ve a la derecha, la pila es ahora [1 2 5]
• No hay hijos de 5, así que pop, stack es ahora [1 2]
• Has agotado a los hijos de 2, así que hazlo, pila ahora es [1]
• Ahora estás de vuelta en el 1 y has terminado la izquierda, así que ve a la derecha al 3, empújalo, la pila está ahora [1 3]
• Ve a la izquierda, la pila es ahora [1 3 6]
• 6 es una hoja, no es lo que estás buscando, entonces pop, stack is [1 3]
• Ahora tienes que ir a la derecha desde 3, empujar, apilar ahora [1 3 7]
• ¡Pero espera! ¡MIRA! ¡Has llegado al nodo que estás buscando! ¡Y mira tu pila! Es el camino que quieres.

Answer 3

Hay 3 soluciones aquí en Java:
https://codereview.stackexchange.com/questions/105136/path-sum-in-binary-tree
Primero, el enfoque recursivo, el segundo con 2 marcas y el último con 2 colas. Espero que esto ayude

Answer 4

Se le proporciona un árbol binario (Nodo raíz) ... y se proporciona una clave que puede o no estar en el árbol. Tienes que encontrar la ruta completa desde la raíz hasta el nodo.

Ejemplo:

                A
           /           /
       B                C
         /               /
          D           E
        /    /           /
      K      L        M
    /
Z

ha dado el nodo Z (o la clave para el nodo) y el nodo A (raíz), por lo que su salida debería ser

ABDKZ

si se da M, la salida debe ser ACEM

public class main_class {
public static void main(String args[] ) {

    //first create tree
    Node rootNode = new Node (''A'' , new Node(''B'',null,
                                             new Node(''D'',
                                                      new Node(''K'',
                                                               new Node(''Z'',null,
                                                               null),null),
                                                      new Node(''L'',null,null))),
                                    new Node(''C'',
                                             new Node(''E'',
                                                      null,
                                                      new Node(''M'',null,null)),null) );

    ArrayList <Node> path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,''Z'',path));
    System.out.println(path);
    path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,''M'',path));
    System.out.println(path);

}
static boolean getPath(Node rootNode, char key, ArrayList<Node> path ){
    //return true if the node is found
    if( rootNode==null)
        return false;
    if (rootNode.getVal()==key){
        path.add(rootNode);
        return true;
    }
    boolean left_check = getPath( rootNode.left,key,path);
    boolean right_check = getPath( rootNode.right,key,path);
    if ( left_check || right_check){
        path.add(rootNode);
        return true;
    }
    return false;

}
static class Node {
    char val;
    Node left;
    Node right;
    public Node( char val, Node left, Node right){
        this.left=left;
        this.right=right;
        this.val=val;
    }
    public char getVal(){
        return val;
    }
   public String toString(){
        return " " + val + " ";
    }
}

}

Answer 5

public List<Node<T>> getPath(T data){
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Boolean found =  getPath(root, stack, data);
        List<Node<T>> path = new ArrayList<Node<T>>();

        if(!found){
            return path;
        }
        return Arrays.asList(stack.toArray((Node<T>[])new Node[stack.size()]));
    }

    public Boolean getPath(Node<T> node, Stack<Node<T>> stack, T data){
        if(node == null){
            return false;
        }
        stack.push(node);

        if(node.data.equals(data)){
            return true;
        }
        Boolean found = getPath(node.left, stack, data) ||
                getPath(node.right, stack, data);

        if(!found ){
            stack.pop();
        }
        return found;
    }