обход BFS слева направо на двоичном дереве

Question

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

Вопрос очень похож на прохождение порядка уровней, как BFS. В BFS мы обычно движемся слева направо на каждом уровне дерева, но здесь, если мы путешествуем слева направо на уровне i, то уровни (i-1) и (i + 1) необходимо перемещать справа налево.

Например:

           2
          / \
         7   5
        / \   \
       2   6   9
          / \   \
         5  11   4

В обычном BFS мы выводим: 2, 7, 5, 2, 6, 9, 5, 11, 4

Но я ищу решение, где мы выводим: 2, 5, 7, 2, 6, 9, 4, 11, 5

Я могу найти решение. Но я хочу посмотреть, найдется ли у кого-нибудь лучшее решение, чем у меня. Я особенно ищу оптимизацию в отношении сложности пространства (размер стека).

Пожалуйста, дайте свою логику в соответствии с языком C ++. Я буду очень признателен, если вы не будете использовать какие-либо контейнеры или STL в своем решении.

---

Основываясь на комментариях, я нашел решение с использованием двух стеков. Мое решение, как показано ниже.

• Создание стека S1 и S2 и очереди Q. В очереди Q будут храниться последние ответы.
• Обратите внимание, что перед добавлением любого стека (S1 или S2) мы сначала поместим его в очередь Q.
• Что бы мы ни извлекали из стека s1, мы поместим его (первого) правого потомка и (затем) левого потомка (в этом порядке) в стек s2. (Помните пункт 2)
• Что бы мы ни извлекали из стека s2, мы поместим его (первого) левого потомка и (затем) правого потомка (в этом порядке) в стек s1. (Помните пункт 2)
• Выскочите из одной стопки и переместите ее в другую, пока обе стопки не опустеют. окончательные записи в очереди будут отвечать.

---

/*
Create Stack S1, S2; // for tmp itr. Both of size log<n>
Create Queue Q; // It will hold ans
*/ 


Q.enqueue(root); //Enqueue the root nood;
S1.enqueue(root); //Fill the stack with somthing to start.



  while(S1||S2){                        // keep spinning untill both stack are empty.
        while(s1){                      //take care of stack S1.
            Node* tmp = S1.pop();       //take top elem;

        if(tmp->right){
            Q.enqueue(tmp->right);
            S2.push(tmp->right);
        }

        if(tmp->left){
            Q.enqueue(tmp->left);
            S2.push(tmp->left);
        }
    }

    while(S2){ //while S2 is not empty
        Node* tmp = S2.pop();

        if(tmp->left){
            Q.enqueue(tmp->left);
            S1.push(tmp->left);
        }

        if(tmp->right){
            Q.enqueue(tmp->right);
            S1.push(tmp->right);
        }

    }
} //End of outher while

while(Q){
    cout<< Q.pop()->data;   //output the entries in desired format.
}

---

Мне кажется, хорошо (дайте мне знать, если это не так). Но все еще задаюсь вопросом, может ли быть какое-либо другое возможное решение (лучше, чем это).

Answer 1

Вместо того, чтобы использовать одну очередь, используйте пару стеков. Когда текущий стек пуст, начните выталкивать узлы из другого и помещать их дочерние элементы в пустую.

Итак, у вас есть

• Нажмите 2 на один из стеков.
• Сдвиньте 2 с него, нажмите 7 5 на другого. Поменяйте местами стеки.
• Pop 5, push 9.
• Pop 7, push 6 2. Поменяйте местами стеки.

Etc.

Вам нужна переменная состояния, чтобы решить, следует ли сначала нажимать влево или вправо.

Answer 2

Я только что попробовал вышеупомянутое предложение, данное Potatoswatter в C #. Я не пробовал запустить его. Пожалуйста, поправьте меня, если что-то нужно изменить.

void BFSTraversePrintzigzag(Node root)  

{  
    bool bLeftToRight = true;  
    Stack<Node> stack1=new Stack<Node>();  
    Stack<Node> stack2=new Stack<Node>();  
    stack1.Push(root);  
    //loop until both the stacks are empty  
    while(stack1.Count>0 ||stack2.Count>0)  
    {  
        //Stack1 will be empty when all the nodes on a level are traversed.   
        if (stack1.Count==0 && stack2.Count>0)  
        {  
            //Swap stack1 and stack2, if stack1 is empty  
            stack1= stack2;  
            while(stack2.Count>0)  
                stack2.Pop();  
            bLeftToRight=!bLeftToRight;  
            //This is the state variable to switch the order from left to right and from Right to left  
        }  
        root=stack1.Pop();  
        Console.WriteLine(root.data) ;  
        if(bLeftToRight)      
        {        
            if(root.left!=null)  
                stack2.Push(root.left);  
            if(root.right!=null)  
                stack2.Push(root.right);  
        }  
        else  
        {  
            if(root.right!=null)  
                stack2.Push(root.right);  
            if(root.left!=null)  
                stack2.Push(root.left);  
        }  
    }  
}  

Answer 3

Если я понимаю, что вы хотите, я бы использовал очередь с приоритетами вместо стека. В качестве ключей для вашей приоритетной очереди вам необходимо сохранить уровень в дереве узла и порядок в пределах этого уровня. Функция сравнения будет использовать уровень в качестве первичного ключа. Для четных уровней он будет использовать порядок в качестве вторичного ключа напрямую, но для нечетных уровней он будет отрицать его. В зависимости от того, рассматриваете ли вы корень дерева уровня 0 или уровня 1, вам может понадобиться поменять, какие уровни используются напрямую по сравнению с отрицательными.