attraversamento ordine di livello di stampa dell'albero binario in modo Zigzag

Question

Devo stampare i nodi di un albero binario utilizzando l'attraversamento di ordine di livello ma a spirale i nodi di livello diverso devono essere stampati a spirale.

per esempio: Se l'albero assomigliare:

L'uscita dovrebbe essere 10 5 20 25 15 6 4.

L'algoritmo i utilizzata è semplice ed è solo una piccola variazione di livello trasversale. Ho appena preso una variabile p.if la variabile è uguale a 1 di stampare l'ordine a un dato livello da sinistra a destra, se è -1 stampa da destra a sinistra.

void getlevel(struct node *root,int n,int p) 
{ 
     if(root==NULL) 
     return; 
     if(n==0) 
     { 
       printf("%d ",root->info); 
       return; 
     } 
     if(n>0) 
     { 
      if(p==1) 
      { 
       getlevel(root->left,n-1,p); 
       getlevel(root->right,n-1,p); 
      } 
      if(p==-1) 
      { 
       getlevel(root->right,n-1,p); 
       getlevel(root->left,n-1,p); 
      } 
     } 
} 

sto ottenendo la risposta, ma il caso peggiore complessità è probabilmente O (n^2) in caso di albero distorta.

Ci può essere un algoritmo migliore per questo compito? ..

mio intero programma è here

Answer 1

Sì.

Si può fare qualcosa di simile al normale traversamento degli ordini di livello.

è necessario utilizzare due pile

1. prima pila per la stampa da sinistra a destra
2. seconda pila per la stampa da destra a sinistra.

Inizia dal nodo radice. Memorizza i bambini in una pila. In ogni iterazione, hai nodi di un livello in uno degli stack. Stampa i nodi e spingi i nodi del livello successivo in un altro stack. Ripeti fino a raggiungere il livello finale.

Complessità temporale O (n) e complessità spaziale O (n).

Answer 2

Psuedocode per l'attraversamento di ordini a livello di spirale di un albero binario.

//Define two stacks S1, S2 

//At each level, 
// S1 carries the nodes to be traversed in that level 
// S2 carries the child nodes of the nodes in S1 

spiralLevelOrder(root) { 
    S1 = new Stack() 
    S2 = new Stack() 
    S1.push(root) 
    spiralLevelOrderRecursion(S1, S2, 1) 
} 

spiralLevelOrderRecursion(S1, S2, level) { 
    while(S1 not empty) { 
    node = S1.pop() 
     visit(node) 
     if (level is odd) { 
      S2.push(node.rightNode) 
      S2.push(node.leftNode) 
     } 
     else { 
      S2.push(node.leftNode) 
      S2.push(node.rightNode) 
     } 
    } 
    if (S2 not empty) 
     spiralLevelOrderRecursion(S2, S1, level+1) 
} 

albero Esempio: 1- (2- (4,5), 3- (5,6)) Formato: root- (leftchild, rightchild)

Applicando la pseudocodice:

spiralLevelOrderRecursion ([1], [], 1)

S2 - [] -> [3] -> [2, 3] 
visit order : 1 

spiralLevelOrderRecursion ([2,3], [], 2)

S2 - [] -> [4] -> [5,4] -> [6, 5, 4] -> [7, 6, 5, 4] 
visit order : 2, 3 

spiralLevelOrderRecursion ([7,6,5,4], [], 3)

visit order : 7, 6, 5, 4 

Answer 3

// semp ++ codice utilizzando due pile

<pre> void zigzag(struct node *root) 
 
     { 
 
      int lefttoright = 1 ; 
 
      struct node *temp ; 
 
      if(root == NULL) 
 
       return ; 
 
      stack<struct node *> current , next ,temp2 ;// temp is used to swap 
 
                 ////current and next    
 
      current.push(root); 
 
      while(!current.empty()) 
 
      {temp = current.top(); 
 
      current.pop(); 
 
      cout<< temp->data << " " ; 
 
      if(lefttoright) 
 
      { if(temp->left) 
 
       next.push(temp->left) ; 
 
       if(temp->right) 
 
       next.push(temp->right) ; 
 
        
 
       
 
       } 
 
      else 
 
       {if(temp->right) 
 
       next.push(temp->right) ; 
 
       if(temp->left) 
 
       next.push(temp->left) ; 
 
       } 
 
      if(current.empty()) // make current as next and next as current 
 
            //to hold next level nodes 
 
      {lefttoright = 1-lefttoright ; 
 
      temp2 = current ; 
 
      current = next ; 
 
      next = temp2 ; 
 
      } 
 
       
 
       
 
      } 
 
      
 
     </pre>

Answer 4

importazione java.util.ArrayList;

importazione java.util.LinkedList;

importazione java.util.Stack;

public class ZigZagTraversal {

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    BinaryTree bt = new BinaryTree(); 
    int[] array = {2,5,1,3,11,7,8,9,4,10,6}; 
    /* 
    *     2 
    *    /\ 
    *    / \ 
    *    / \ 
    *    5  1 
    *   /\ /\ 
    *   / \ / \ 
    *   3 11 7  8 
    *  /\ /\ 
    *   9 4 10 6 
    * 
    * */ 
    bt=BinaryTree.buildATree(bt, array); 
    //BinaryTree.inOrderTraversal(bt); 
    zigZagTraversal(llForAllNodesAtEachDepth(bt)); 
    zigZagDisplay(bt); 
} 
public static void zigZagDisplay(BinaryTree bt){ 
    Stack<BinaryTree> s = new Stack<>(); 
    if(s.isEmpty()) 
     s.push(bt); 
    boolean flag = true; 
    while(!s.isEmpty()){ 
     Stack<BinaryTree> temp = new Stack<>(); 
     while(!s.isEmpty()){ 
      BinaryTree b = s.pop(); 
      System.out.print(b.data+" "); 
      if(flag){ 
       if(b.left!=null) 
        temp.push(b.left); 
       if(b.right!=null) 
        temp.push(b.right); 
      } 
      else{ 
       if(b.right!=null) 
        temp.push(b.right); 
       if(b.left!=null) 
        temp.push(b.left); 
      } 
     } 
     s=temp; 
     flag=!flag; 
    } 
} 
public static ArrayList<LinkedList<BinaryTree>> llForAllNodesAtEachDepth(BinaryTree bt){ 
    ArrayList<LinkedList<BinaryTree>> res = new ArrayList<LinkedList<BinaryTree>>(); 
    return createLlForAllNodesAtEachDepth(res,bt, 0); 
} 
public static ArrayList<LinkedList<BinaryTree>> createLlForAllNodesAtEachDepth(ArrayList<LinkedList<BinaryTree>> res, BinaryTree bt, int level){ 
    if(bt==null) 
     return null; 
    if(level==res.size()){ 
     LinkedList<BinaryTree> list = new LinkedList<BinaryTree>(); 
     list.add(bt); 
     res.add(list); 
     createLlForAllNodesAtEachDepth(res,bt.left,level+1); 
     createLlForAllNodesAtEachDepth(res,bt.right,level+1); 
    } 
    else{ 
     res.get(level).add(bt); 
     createLlForAllNodesAtEachDepth(res,bt.left,level+1); 
     createLlForAllNodesAtEachDepth(res,bt.right,level+1); 
    } 
    return res; 
} 
public static void zigZagTraversal(ArrayList<LinkedList<BinaryTree>> res){ 
    boolean flag=true; 
    for(int i=0;i<res.size();i++){ 
     LinkedList<BinaryTree> temp = res.get(i); 
     if(flag){ 
      for(int j=0;j<temp.size();j++){ 
       System.out.print(temp.get(j).data+" -> "); 
      } 
      flag=false; 
     } 
     else{ 
      for(int j=temp.size()-1;j>=0;j--){ 
       System.out.print(temp.get(j).data+" -> "); 
      } 
      flag=true; 
     } 
     System.out.println(); 
    } 
} 

}

Answer 5

Il seguente codice farà il lavoro:

linguistiche: il Java

// Algorithm for printing nodes in Zigzag order(zigzag tree traversal) 
static void zigzagTreeTraversal(Node root) 
{ 
    int count=0,c=1,i=0; 
    boolean odd=false; 
    Queue<Node> queue=new LinkedList<Node>(); 
    Node temp = null; 
    queue.add(root); 
    System.out.print("Printing Tree Traversal in Zigzag form :"); 
    while(true) 
    { 
     if(queue.isEmpty()) 
     { 
      break; 
     } 

     for(i=0;i<c;i++) 
     { 
      temp=queue.remove(); 
      System.out.print(", " + temp.data); 
      if(odd) 
      { 
       if(temp.right!=null) 
       { 
        queue.add(temp.right); 
        count++; 
       } 

       if(temp.left!=null) 
       { 
        queue.add(temp.left); 
        count++; 
       } 

      } 
      else 
      { 
       if(temp.left!=null) 
       { 
        queue.add(temp.left); 
        count++; 
       } 
       if(temp.right!=null) 
       { 
        queue.add(temp.right); 
        count++; 
       } 

      } 
     } 
     c=count; 
     count=0; 
     odd=!odd; 
    } 
}