обход порядка уровня на уровне двоичного дерева по методу зигзага

Question

Я должен печатать узлы двоичного дерева, используя обход уровня, но в спиральной форме. I.e узлы на разных уровнях должны быть напечатаны в виде спирали.

для например: Если дерево выглядит следующим образом:

Выход должен быть 10 5 20 25 15 6 4.

алгоритм я использовал простой и лишь небольшая вариация обхода уровня порядка. Я просто взял переменную p.if, если переменная равна 1, чем печатать заказ на заданном уровне слева направо, если он -1 печатает справа налево.

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); 
      } 
     } 
} 

Я получаю ответ, но худший случай сложности, вероятно, O (N^2) в случае наклонного дерева.

Может ли быть лучше алгоритм для решения этой задачи? ..

Моя вся программа here

Answer 1

Да.

Вы можете сделать что-то похожее на обычный ход порядка.

Вы должны использовать два стека

1. первый стек для печати слева направо
2. второй стек для печати справа налево.

Начать с корневого узла. Храните его в одной папке. На каждой итерации у вас есть узлы одного уровня в одном из стеков. Распечатайте узлы и нажмите узлы следующего уровня в другом стеке. Повторяйте до достижения конечного уровня.

Сложность времени O (n) и сложность пространства O (n).

Answer 2

Psuedocode для обращения за уровнем спирального двоичного дерева.

//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) 
} 

Пример дерева: 1- (2- (4,5), 3- (5,6)) формат: корне- (LeftChild, RightChild)

Применяя псевдокод:

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

// простой C++ кода с помощью двух стеков

<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

импорт java.util.ArrayList;

импорт java.util.LinkedList;

импорт java.util.Stack;

общественного класса 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

Следующий код будет делать работу:

Используемый язык: 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; 
    } 
}