Обход порядка уровня двоичного дерева по типу зигзага - программирование
Подтвердить что ты не робот

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

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

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

Выход должен быть 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) в случае перекошенного дерева.

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

Вся моя программа здесь

4b9b3361

ОТВЕТЫ

Ответ 1

Да.

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

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

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

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

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

Ответ 2

Psedocode для обхода порядка в спиральном двоичном дереве.

//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)) format: root- (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

Ответ 3

Следующий код выполнит задание:

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

Ответ 4

import java.util.ArrayList;

импортировать java.util.LinkedList;

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

}

Ответ 5

//простой код С++ с использованием двух стеков

<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>