Итеративный обход предзаказа (Debug) - PullRequest
Новая
       1

Итеративный обход предзаказа (Debug)

1 голос
/ 17 марта 2012

Вот итерационная версия обхода предзаказа. Идея состоит в том, чтобытолкнуть корень в стек.Если левый дочерний элемент не равен NULL. Нажмите левый дочерний элемент и root = root-> left Else root = Top of stack; Pop; нажмите правый дочерний элемент и root = root-> right

Он работает на некоторых деревьях, нодля некоторых входных деревьев он печатает дублирующееся значение. Поведение стека удивительно. Как оно меняется с (4 5 6 8) на (4 6 8)? 

    void preorder(node* root)
    {stack<node*> st;
     st.push(root);
     cout<<root->val<<" \n ";
     while(!st.empty())
      {if(root->left!=NULL)
         {st.push(root->left);
          cout<<st.top()->val<<" ";
         // printstack(st);
          root=root->left;
          }
       else{root=st.top();
            st.pop();
           if(root->right!=NULL)
            {st.push(root->right);
             cout<<st.top()->val<<" ";   
             //printstack(st);
              root=root->right;
             }
           }
        }
      }

Хелперская функция printstack, используемая для отладки

     void printstack(stack<node*> s)
      {stack<node*> t;
      t=s;
      while(!t.empty())
       {cout<<t.top()->val<<" ";
       t.pop();
       }
      }

Для этого дерева ввода печатная стопка находится ниже.Выход предварительного заказа:
8 3 1 6 5 4 4 7 9 

<br>
                  <strong><em>_</em>__<em>_</em>__</strong><em>8</em>_
                 /                \
             <strong>__</strong><em>3</em><strong>_          9
            /        \
            1      ___6</strong>
                     /    \
                     5      7
                    /
                   4

3 8

1 3 8 

6 8

5 68

4 5 6 8

4 6 8 // Какова вершина стека 4 ?? Должно быть 5, стек (5 6 8) 

7 8

  9

Ответы [ 3 ]

0 голосов
/ 17 марта 2012

Предварительный заказ

Инициализация: Вставить корневой узел в стек 

While(Stack not Emtpy)
{
  Node = Stack.pop();
  print Node;
  Push Node->right onto the Stack (pushing first, as I need to process left tree first. 
                               Stack is LIFO)
  Push Node->left onto the Stack
 }

Приведенный выше псевдокод должен печатать обход предварительного заказа.

0 голосов
/ 02 марта 2014

Вот правильный код, который является модификацией вашего кода. Просто посмотрите изменения

Пустой предзаказ (узел * r1) 

    {stack<node*> st;
     st.push(r1);
     node* root;
     root=r1;
     cout<<root->val<<" ";
     while(!st.empty())
      {if(root->left!=NULL)
         {st.push(root->left);
          cout<<st.top()->val<<" ";
          root=root->left;
          }
       else{root=st.top();
            st.pop();
           if(root->right!=NULL)
            {st.push(root->right);
             cout<<st.top()->val<<" ";   
              root=root->right;
             }
            else
            root->left=NULL;
           }
        }
      }
0 голосов
/ 17 марта 2012

Проблема возникает на узлах, которые оставили детей, но не правы.Когда у узла есть правильный дочерний элемент, последний блок if меняет корень до следующей итерации, но без него корень не переключается.Затем в следующий раз мы увидим корень (который уже извлечен из стека), у которого есть левый дочерний элемент, поэтому его левый дочерний элемент помещается в стек и снова посещается.

Надеюсь, что это поможет.

...