Рубрики

Внутренний обход дерева без рекурсии

Использование стека является очевидным способом обхода дерева без рекурсии. Ниже приведен алгоритм обхода двоичного дерева с использованием стека. Смотрите это для пошагового пошагового выполнения алгоритма.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack.
     b) Print the popped item, set current = popped_item->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Давайте рассмотрим дерево ниже, например

            1
          /   \
        2      3
      /  \
    4     5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
     current -> 1
     push 1: Stack S -> 1
     current -> 2
     push 2: Stack S -> 2, 1
     current -> 4
     push 4: Stack S -> 4, 2, 1
     current = NULL

Step 4 pops from S
     a) Pop 4: Stack S -> 2, 1
     b) print "4"
     c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything. 

Step 4 pops again.
     a) Pop 2: Stack S -> 1
     b) print "2"
     c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
     Stack S -> 5, 1
     current = NULL

Step 4 pops from S
     a) Pop 5: Stack S -> 1
     b) print "5"
     c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
     a) Pop 1: Stack S -> NULL
     b) print "1"
     c) current -> 3 /*right of 5 */  

Step 3 pushes 3 to stack and makes current NULL
     Stack S -> 3
     current = NULL

Step 4 pops from S
     a) Pop 3: Stack S -> NULL
     b) print "3"
     c) current = NULL /*right of 3 */  

Traversal is done now as stack S is empty and current is NULL. 

C ++

// C ++ программа для печати обхода заказа
// используя стек.
#include<bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct Node

{

    int data;

    struct Node* left;

    struct Node* right;

    Node (int data)

    {

        this->data = data;

        left = right = NULL;

    }

};

  
/ * Итерационная функция для дерева заказов

   обход * /

void inOrder(struct Node *root)

{

    stack<Node *> s;

    Node *curr = root;

  

    while (curr != NULL || s.empty() == false)

    {

        / * Достичь самого левого узла

           Curr Node * /

        while (curr !=  NULL)

        {

            / * разместить указатель на узел дерева на

               стек перед прохождением

              левое поддерево узла * /

            s.push(curr);

            curr = curr->left;

        }

  

        / * Ток должен быть НЕДЕЙСТВИТЕЛЕН в этой точке * /

        curr = s.top();

        s.pop();

  

        cout << curr->data << " ";

  

        / * мы посетили узел и его

           левое поддерево Теперь это правильно

           очередь поддерева * /

        curr = curr->right;

  

    } / * конец времени * /

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  

    / * Построенное двоичное дерево

              1

            / /

          2 3

        / /

      4 5

    * /

    struct Node *root = new Node(1);

    root->left        = new Node(2);

    root->right       = new Node(3);

    root->left->left  = new Node(4);

    root->left->right = new Node(5);

  

    inOrder(root);

    return 0;

}

С

#include<stdio.h>
#include<stdlib.h>
#define bool int

  
/ * В двоичном дереве tNode есть данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct tNode

{

   int data;

   struct tNode* left;

   struct tNode* right;

};

  
/ * Структура стекового узла. Реализация связанного списка используется для

   стек. Узел стека содержит указатель на узел дерева и указатель на

   следующий узел стека * /

struct sNode

{

  struct tNode *t;

  struct sNode *next;

};

  
/ * Связанные со стеком функции * /

void push(struct sNode** top_ref, struct tNode *t);

struct tNode *pop(struct sNode** top_ref);

bool isEmpty(struct sNode *top);

  
/ * Итерационная функция для обхода дерева заказов * /

void inOrder(struct tNode *root)

{

  / * установить текущий корень двоичного дерева * /

  struct tNode *current = root;

  struct sNode *s = NULL;  / * Инициализировать стек s * /

  bool done = 0;

  

  while (!done)

  {

    / * Достигнуть самого левого tNode текущего tNode * /

    if(current !=  NULL)

    {

      / * поместить указатель на узел дерева в стеке перед обходом

        левое поддерево узла * /

      push(&s, current);                                               

      current = current->left;  

    }

         

    / * вернуться из пустого поддерева и посетить tNode

       на вершине стека; однако, если стек пуст,

      вы сделали */

    else                                                              

    {

      if (!isEmpty(s))

      {

        current = pop(&s);

        printf("%d ", current->data);

  

        / * мы посетили узел и его левое поддерево.

          Теперь настала очередь правого поддерева * /

        current = current->right;

      }

      else

        done = 1; 

    }

  } / * конец времени * /  
}     

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для перемещения элемента в sNode * /

void push(struct sNode** top_ref, struct tNode *t)

{

  / * выделить tNode * /

  struct sNode* new_tNode =

            (struct sNode*) malloc(sizeof(struct sNode));

  

  if(new_tNode == NULL)

  {

     printf("Stack Overflow \n");

     getchar();

     exit(0);

  }            

  

  / * вставить данные * /

  new_tNode->t  = t;

  

  / * связать старый список с новым tNode * /

  new_tNode->next = (*top_ref);   

  

  / * переместить голову, чтобы указать на новый tNode * /

  (*top_ref)    = new_tNode;

}

  
/ * Функция возвращает истину, если стек пуст, иначе ложь * /

bool isEmpty(struct sNode *top)

{

   return (top == NULL)? 1 : 0;

}   

  
/ * Функция извлечения элемента из стека * /

struct tNode *pop(struct sNode** top_ref)

{

  struct tNode *res;

  struct sNode *top;

  

  / * Если sNode пуст, то ошибка * /

  if(isEmpty(*top_ref))

  {

     printf("Stack Underflow \n");

     getchar();

     exit(0);

  }

  else

  {

     top = *top_ref;

     res = top->t;

     *top_ref = top->next;

     free(top);

     return res;

  }

}

  
/ * Вспомогательная функция, которая выделяет новый tNode с

   данные даны и NULL левый и правый указатели. * /

struct tNode* newtNode(int data)

{

  struct tNode* tNode = (struct tNode*)

                       malloc(sizeof(struct tNode));

  tNode->data = data;

  tNode->left = NULL;

  tNode->right = NULL;

  

  return(tNode);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  

  / * Построенное двоичное дерево

            1

          / /

        2 3

      / /

    4 5

  * /

  struct tNode *root = newtNode(1);

  root->left        = newtNode(2);

  root->right       = newtNode(3);

  root->left->left  = newtNode(4);

  root->left->right = newtNode(5); 

  

  inOrder(root);

  

  getchar();

  return 0;

}

Джава

// нерекурсивная Java-программа для обхода inorder

import java.util.Stack;

  
/ * Класс, содержащий левого и правого потомка
текущий узел и значение ключа * /

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
/ * Класс для печати обхода заказа * /

class BinaryTree

{

    Node root;

    void inorder()

    {

        if (root == null)

            return;

  

  

        Stack<Node> s = new Stack<Node>();

        Node curr = root;

  

        // пройти через дерево

        while (curr != null || s.size() > 0)

        {

  

            / * Достичь самого левого узла

            Curr Node * /

            while (curr !=  null)

            {

                / * разместить указатель на узел дерева на

                   стек перед прохождением

                  левое поддерево узла * /

                s.push(curr);

                curr = curr.left;

            }

  

            / * Ток должен быть НЕДЕЙСТВИТЕЛЕН в этой точке * /

            curr = s.pop();

  

            System.out.print(curr.data + " ");

  

            / * мы посетили узел и его

               левое поддерево Теперь это правильно

               очередь поддерева * /

            curr = curr.right;

        }

    }

  

    public static void main(String args[])

    {

  

        / * создание бинарного дерева и ввод

        узлы * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.inorder();

    }

}

питон

# Программа Python для обхода inorder без рекурсии

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Итеративная функция для обхода дерева заказов

def inOrder(root):

      

    # Установить текущий корень двоичного дерева

    current = root 

    stack = [] # инициализировать стек

    done = 0 

      

    while True:

          

        # Достичь самого левого узла текущего узла

        if current is not None:

              

            # Поместить указатель на узел дерева в стеке

            # перед обходом левого поддерева узла

            stack.append(current)

          

            current = current.left 

  

          

        # BackTrack из пустого поддерева и посещение узла

        # вверху стека; однако, если стек

        # пусто вы сделали

        elif(stack):

            current = stack.pop()

            print(current.data, end=" ") # Python 3 печать

          

            # Мы посетили узел и его левый

            # поддерево. Теперь настала очередь правильного поддерева

            current = current.right 

  

        else:

            break

       

    print()

  
# Программа драйвера для проверки вышеуказанной функции

  
"" "Построенное двоичное дерево

            1

          / /

         2 3

       / /

      4 5 "" "

  

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

  
inOrder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// нерекурсивная C # программа для обхода по порядку

using System;

using System.Collections.Generic;

  

  
/ * Класс, содержащий левого и правого потомка
текущий узел и значение ключа * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
/ * Класс для печати обхода заказа * /

public class BinaryTree

{

    public Node root;

    public virtual void inorder()

    {

        if (root == null)

        {

            return;

        }

  

  

        Stack<Node> s = new Stack<Node>();

        Node curr = root;

  

        // пройти через дерево

        while (curr != null || s.Count > 0)

        {

  

            / * Достичь самого левого узла

            Curr Node * /

            while (curr != null)

            {

                / * разместить указатель на узел дерева на

                   стек перед прохождением

                  левое поддерево узла * /

                s.Push(curr);

                curr = curr.left;

            }

  

            / * Ток должен быть НЕДЕЙСТВИТЕЛЕН в этой точке * /

            curr = s.Pop();

  

            Console.Write(curr.data + " ");

  

            / * мы посетили узел и его

               левое поддерево Теперь это правильно

               очередь поддерева * /

            curr = curr.right;

        }

    }

  

    public static void Main(string[] args)

    {

  

        / * создание бинарного дерева и ввод

        узлы * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.inorder();

    }

}

  
// Этот код предоставлен Shrikant13

Выход:

Рекомендуемые посты:

Внутренний обход дерева без рекурсии

0.00 (0%) 0 votes