límite de impresión del árbol binario

Question

Cómo imprimir el marco exterior de un árbol binario.

1. la orden es de arriba a abajo, izquierda a derecha, luego hacia abajo al principio de la impresión
2. todo nodo leftest y los nodos más acertada
3. imprimir todos los nodos hoja

4. de impresión todos los nodos que sólo tiene 1 hoja

     100 
        / \ 
        50  150 
       /\ /
       24 57 130 
   /\ \ \ 
   12 30 60 132 
   

por ejemplo: la salida debe ser 100, 50, 24, 12, 30, 57, 60, 130, 132, 150

Si escribimos tres funciones diferentes para imprimir nodos izquierdos, nodos hoja y nodos derechos, se puede resolver fácilmente pero se necesita O (n + 2logn) tiempo.

También estoy buscando un enfoque O (n), pero la condición es que cada nodo debe visitarse una sola vez, no desea esta parte adicional O (2logn).

Answer 1

Puede lograrlo con el algoritmo de Euler Tour aplicado a su árbol. Ver esto link:

O (si tiene acceso) el libro de Goodrich et. otros (enlace. here)

espero que esto ayude a

Answer 2

parece un problema de trabajo a domicilio, pero necesito la práctica. No he hecho nada con la recursión en una década.

void SimpleBST::print_frame() 
{ 
    if (root != NULL) 
    { 
     cout << root->data; 

     print_frame_helper(root->left, true, false); 
     print_frame_helper(root->right, false, true); 
     cout << endl; 
    } 
} 

void SimpleBST::print_frame_helper(Node * node, bool left_edge, bool right_edge) 
{ 
    if (node != NULL) 
    { 
     if (left_edge) 
     cout << ", " << node->data; 

     print_frame_helper(node->left, left_edge && true, false); 

     if ((!left_edge) && (!right_edge)) 
     if ((node->left == NULL) || (node->right == NULL)) 
      cout << node->data << ", "; 

     print_frame_helper(node->right, false, right_edge && true); 

     if (right_edge) 
     cout << ", " << node->data; 
    } 
} 

Answer 3

Esto se puede hacer en O (n). Es decir, visitamos cada nodo del árbol una sola vez. La lógica es la siguiente Mantener dos variables izquierda y derecha e inicializarlas a cero. Cuando siempre hay llamada recursiva a la subasta del lado izquierdo dejó por 1 Cuando siempre hay llamada recursiva a montar incremento lado derecho por 1

A partir de la raíz, hacer finde recorrido y comprobar si derecho es cero, eso significa que nunca hicimos una llamada recursiva a la derecha. Si sí, imprimir nodo, esto significa que estamos imprimiendo todos los nodos más a la izquierda del árbol. Si derecho es distinto de cero, no se consideran límites, así que busque nodos hoja e imprímalos.

En el recorrido de Inorder después de que las llamadas al árbol secundario izquierdo hayan terminado, salta a la raíz y luego hacemos una llamada recursiva para el subárbol derecho. Ahora compruebe primero los nodos de hojas e imprímalos, luego verifique si dejó es cero, eso significa que hicimos una llamada recursiva a la izquierda, por lo que no se consideran límites. Si dejó es un nodo de impresión cero, esto significa que estamos imprimiendo todos los nodos más a la derecha del árbol.

El fragmento de código es

void btree::cirn(struct node * root,int left,int right) 
{ 



if(root == NULL) 
    return; 
if(root) 
{ 

    if(right==0) 
    { 

     cout<<root->key_value<<endl; 
    } 

    cirn(root->left,left+1,right); 




if(root->left==NULL && root->right==NULL && right>0) 
    { 

      cout<<root->key_value<<endl; 
    } 





    cirn(root->right,left,right+1); 
    if(left==0) 
    { 

     if(right!=0) 
     { 
      cout<<root->key_value<<endl; 
     } 


    } 




} 

}

Answer 4

La solución se puede hacer por la que atraviesa el árbol en pre-orden - O (n).
Encuentra el código de muestra a continuación. Source and some explanation.

Código de ejemplo en Java:

public class Main { 
    /** 
    * Prints boundary nodes of a binary tree 
    * @param root - the root node 
    */ 
    public static void printOutsidesOfBinaryTree(Node root) { 

     Stack<Node> rightSide = new Stack<>(); 
     Stack<Node> stack = new Stack<>(); 

     boolean printingLeafs = false; 
     Node node = root; 

     while (node != null) { 

      // add all the non-leaf right nodes left 
      // to a separate stack 
      if (stack.isEmpty() && printingLeafs && 
        (node.left != null || node.right != null)) { 
       rightSide.push(node); 
      } 

      if (node.left == null && node.right == null) { 
       // leaf node, print it out 
       printingLeafs = true; 
       IO.write(node.data); 
       node = stack.isEmpty() ? null : stack.pop(); 
      } else { 
       if (!printingLeafs) { 
        IO.write(node.data); 
       } 

       if (node.left != null && node.right != null) { 
        stack.push(node.right); 
       } 
       node = node.left != null ? node.left : node.right; 
      } 
     } 

     // print out any non-leaf right nodes (if any left) 
     while (!rightSide.isEmpty()) { 
      IO.write(rightSide.pop().data); 
     } 
    } 
} 

Answer 5

Algo:

1. impresión del límite izquierdo
2. impresión de las hojas de impresión
3. la frontera derecha

---

void getBoundaryTraversal(TreeNode t) { 
     System.out.println(t.t); 
     traverseLeftBoundary(t.left); 
     traverseLeafs(t); 
     //traverseLeafs(t.right); 
     traverseRightBoundary(t.right); 
    } 
    private void traverseLeafs(TreeNode t) { 
     if (t == null) { 
      return; 
     } 
     if (t.left == null && t.right == null) { 
      System.out.println(t.t); 
      return; 
     } 
     traverseLeafs(t.left); 
     traverseLeafs(t.right); 
    } 
    private void traverseLeftBoundary(TreeNode t) { 
     if (t != null) { 
      if (t.left != null) { 
       System.out.println(t.t); 
       traverseLeftBoundary(t.left); 
      } else if (t.right != null) { 
       System.out.println(t.t); 
       traverseLeftBoundary(t.right); 
      } 
     } 
    } 

    private void traverseRightBoundary(TreeNode t) { 
     if (t != null) { 
      if (t.right != null) { 
       traverseRightBoundary(t.right); 
       System.out.println(t.t); 
      } else if (t.left != null) { 
       traverseLeafs(t.left); 
       System.out.println(t.t); 
      } 
     } 
    } 

---

TreeNode definición:

class TreeNode<T> { 

    private T t; 
    private TreeNode<T> left; 
    private TreeNode<T> right; 

    private TreeNode(T t) { 
     this.t = t; 
    } 
} 

Answer 6

Aquí hay una solución simple:

def printEdgeNodes(root, pType, cType): 
    if root is None: 
     return 
    if pType == "root" or (pType == "left" and cType == "left") or (pType == "right" and cType == "right"): 
     print root.val 
    if root.left is None and root.right is None: 
     print root.val 
    if pType != cType and pType != "root": 
     cType = "invalid" 
    printEdgeNodes(root.left, cType, "left") 

def printEdgeNodes(root): 
    return printEdgeNodes(root, "root", "root") 

Answer 7

Usted puede ir de forma recursiva a través de cada nodo y control al imprimir, aquí es el javascript co de snippet.

function findBtreeBoundaries(arr, n, leftCount, rightCount) { 
    n = n || 0; 
    leftCount = leftCount || 0; 
    rightCount = rightCount || 0; 

    var length = arr.length; 
    var leftChildN = 2*n + 1, rightChildN = 2*n + 2; 

    if (!arr[n]) { 
    return; 
    } 

    // this is the left side of the tree 
    if (rightCount === 0) { 
    console.log(arr[n]); 
    } 

    // select left child node 
    findBtreeBoundaries(arr, leftChildN, leftCount + 1, rightCount); 

    // this is the bottom side of the tree 
    if (leftCount !== 0 && rightCount !== 0) { 
    console.log(arr[n]); 
    } 

    // select right child node 
    findBtreeBoundaries(arr, rightChildN, leftCount, rightCount + 1); 

    // this is the right side of the tree 
    if (leftCount === 0 && rightCount !== 0) { 
    console.log(arr[n]); 
    } 

} 

findBtreeBoundaries([100, 50, 150, 24, 57, 130, null, 12, 30, null, 60, null, 132]);