Ітеративний обхід попереднього замовлення  


Рівень складності Легко
Часто запитують у Амазонка Google JP Morgan Microsoft Morgan Stanley Убер
Дерево Обхід дерева

У задачі “Ітеративне обхід попереднього замовлення” зазначено, що вам дано бінарне дерево, і тепер вам потрібно знайти обхід попереднього замовлення дерева. Нам потрібно знайти обхід попереднього замовлення за допомогою ітераційного методу, а не рекурсивного підходу.

Приклад  

Ітеративний обхід попереднього замовленняPin

 

5 7 9 6 1 4 3

Підхід до друку  

Постановка проблеми просить нас надрукувати обхід попереднього замовлення даного двійкового дерева за допомогою ітераційного методу. Як правило, ми використовуємо рекурсивний метод, оскільки це простіше. Але іноді пропонується вирішити проблему за допомогою ітерації. Таким чином, ми тут зобов’язані виконати ітераційний обхід дерева перед замовленням.

Раніше ми використовували рекурсія щоб надрукувати обхід. Отже, щоб замінити рекурсію, ми повинні використовувати a стек структура даних. Отже, ми будемо використовувати структуру даних стеку для зберігання вузлів, які будуть потрібні згодом. Спочатку в обробці попереднього замовлення ми друкуємо корінь, потім рекурсивно друкуємо ліве піддерево, а в кінці рекурсивно друкуємо праве піддерево. У цьому алгоритмі ми будемо запускати цикл, який буде виконуватися до тих пір, поки наш поточний вузол не буде нульовим. І тоді ми будемо продовжувати зберігати потрібну дитину в стосі, якщо потрібна дитина існує. Потім переходимо до лівої дитини. Якщо лівий дочірній елемент дорівнює нулю, ми видаляємо елементи зі стеку і призначаємо їх поточним вузлом. Таким чином, врешті-решт, ми б об'їхали дерево попередньо.

Дивись також
Обхід порядку двійкового дерева зигзагом

код  

Код C ++ для друку ітеративного обходу попереднього замовлення

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void preorder(node* root){
    // create a stack
    stack<node*> s;

    while(root){
        // print the current node
        cout<<root->data<<" ";
        
        // if current node has right sub-tree
        // then store it and use it afterwards
        if(root->right)
            s.push(root->right);
        // now move to left child of current node
        // if the left child does not exists 
        // then in the next condition we will move up in the tree
        // and assign the right children which 
        // we have been storing the stack
        root = root->left;
        if(!root && !s.empty()){
                root = s.top(), s.pop();
        }
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  preorder(root);
}
5 7 9 6 1 4 3

Код Java для друку ітеративного обходу попереднього замовлення

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void preorder(node root){
      // create a stack
      Stack<node> s = new Stack<node>();

      while(root != null){
          // print the current node
          System.out.print(root.data+" ");

          // if current node has right sub-tree
          // then store it and use it afterwards
          if(root.right != null)
              s.add(root.right);
          // now move to left child of current node
          // if the left child does not exists
          // then in the next condition we will move up in the tree
          // and assign the right children which
          // we have been storing the stack
          root = root.left;
          if(root == null && !s.empty()){
                  root = s.peek();
                  s.pop();
          }
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    preorder(root);
  }
}
5 7 9 6 1 4 3

Аналіз складності  

Складність часу

O (N), оскільки ми об'їхали всі елементи дерева. Таким чином, часова складність є лінійною.

Дивись також
Розчин Leetcode для коштовностей та каменів

Складність простору

O (H), у гіршому випадку кожен з вузлів може мати правильну дитину. Тому що ми зберігаємо праву дочірню частину кожного вузла на шляху до лівої дочірньої. Таким чином, ми можемо зберігати максимум O (H) вузлів у стеку.