Рубрики

Inorder Tree Traversal без рекурсии и без стека!

Используя Morris Traversal, мы можем обходить дерево без использования стека и рекурсии. Идея Morris Traversal основана на бинарном дереве с резьбой . В ходе этого обхода мы сначала создаем ссылки на преемника Inorder и печатаем данные, используя эти ссылки, и, наконец, возвращаем изменения, чтобы восстановить исходное дерево.

1. Initialize current as root 
2. While current is not NULL
   If the current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as the right child of the rightmost 
         node in current's left subtree
      b) Go to this left child, i.e., current = current->left

Хотя дерево модифицируется путем обхода, после завершения оно возвращается к своей первоначальной форме. В отличие от обхода на основе стека , для этого обхода не требуется дополнительного места.

C ++

#include <stdio.h>
#include <stdlib.h>

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

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

struct tNode {

    int data;

    struct tNode* left;

    struct tNode* right;

};

  
/ * Функция для обхода двоичного дерева без рекурсии и

   без стека * /

void MorrisTraversal(struct tNode* root)

{

    struct tNode *current, *pre;

  

    if (root == NULL)

        return;

  

    current = root;

    while (current != NULL) {

  

        if (current->left == NULL) {

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

            current = current->right;

        }

        else {

  

            / * Найти по порядку предшественника текущего * /

            pre = current->left;

            while (pre->right != NULL && pre->right != current)

                pre = pre->right;

  

            / * Сделать текущий в качестве правого потомка своего порядка

               предшественник * /

            if (pre->right == NULL) {

                pre->right = current;

                current = current->left;

            }

  

            / * Восстановить изменения, сделанные в части «если», для восстановления

               исходное дерево, т.е. исправить правильного ребенка

               предшественника * /

            else {

                pre->right = NULL;

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

                current = current->right;

            } / * Конец условия if-> right == NULL * /

        } / * Конец условия if current-> left == NULL * /

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

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вспомогательная функция, которая выделяет новый tNode с

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

struct tNode* newtNode(int data)

{

    struct tNode* node = new tNode;

    node->data = data;

    node->left = NULL;

    node->right = NULL;

  

    return (node);

}

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

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

  

    MorrisTraversal(root);

  

    return 0;

}

Джава

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

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

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

class tNode {

    int data;

    tNode left, right;

  

    tNode(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

    tNode root;

  

    / * Функция для обхода двоичного дерева без рекурсии и

       без стека * /

    void MorrisTraversal(tNode root)

    {

        tNode current, pre;

  

        if (root == null)

            return;

  

        current = root;

        while (current != null) {

            if (current.left == null) {

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

                current = current.right;

            }

            else {

                / * Найти по порядку предшественника текущего * /

                pre = current.left;

                while (pre.right != null && pre.right != current)

                    pre = pre.right;

  

                / * Сделать текущий правым потомком своего предшественника по порядку * /

                if (pre.right == null) {

                    pre.right = current;

                    current = current.left;

                }

  

                / * Отменить изменения, сделанные в части «если», чтобы восстановить

                    исходное дерево, т. е. исправление правого потомка предшественника * /

                else {

                    pre.right = null;

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

                    current = current.right;

                } / * Конец условия if-> right == NULL * /

  

            } / * Конец условия if current-> left == NULL * /

  

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

    }

  

    public static void main(String args[])

    {

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

               1

             / /

            2 3

          / /

        4 5

        * /

        BinaryTree tree = new BinaryTree();

        tree.root = new tNode(1);

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

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

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

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

  

        tree.MorrisTraversal(tree.root);

    }

}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

питон

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

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

class Node:

      

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

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

def MorrisTraversal(root):

      

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

    current = root 

      

    while(current is not None):

          

        if current.left is None:

            print current.data,

            current = current.right

        else:

            # Найти по порядку предшественника текущего

            pre = current.left

            while(pre.right is not None and pre.right != current):

                pre = pre.right

   

            # Сделать текущий правым потомком своего предшественника по порядку

            if(pre.right is None):

                pre.right = current

                current = current.left

                  

            # Вернуть изменения, сделанные в if part, чтобы восстановить

            # оригинальное дерево, т.е. исправление правого потомка предшественника

            else:

                pre.right = None

                print current.data,

                current = current.right

              
# Драйвер программы для проверки вышеуказанной функции
«»»
Построенное двоичное дерево

            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)

  
MorrisTraversal(root)

  
# Этот код предоставлен Навином Айли

C #

// C # программа для печати обхода заказа
// без рекурсии и стека

using System;

  
/ * Бинарное дерево tNode содержит данные,

    указатель на левого ребенка

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

  

class BinaryTree 

{

    tNode root;

      

public class tNode 

{

    public int data;

    public tNode left, right;

  

    public tNode(int item)

    {

        data = item;

        left = right = null;

    }

}

    / * Функция для обхода бинарного дерева без

     рекурсия и без стека * /

    void MorrisTraversal(tNode root)

    {

        tNode current, pre;

  

        if (root == null)

            return;

  

        current = root;

        while (current != null)

        {

            if (current.left == null

            {

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

                current = current.right;

            }

            else 

            {

                / * Найти по порядку предшественника текущего * /

                pre = current.left;

                while (pre.right != null && pre.right != current)

                    pre = pre.right;

  

                / * Сделать текущий как правильный ребенок

                своего предшественника по порядку * /

                if (pre.right == null

                {

                    pre.right = current;

                    current = current.left;

                }

  

                / * Отменить изменения, сделанные в

                если часть, чтобы восстановить оригинал

                дерево, т.е. исправить правильного ребенка

                предшественника * /

                else

                {

                    pre.right = null;

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

                    current = current.right;

                } / * Конец условия if-> right == NULL * /

  

            } / * Конец условия if current-> left == NULL * /

  

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

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

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

            1

            / /

            2 3

        / /

        4 5

        * /

        BinaryTree tree = new BinaryTree();

        tree.root = new tNode(1);

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

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

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

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

  

        tree.MorrisTraversal(tree.root);

    }

}

  
// Этот код был добавлен
// Арнаб Кунду


Выход:

4 2 5 1 3

Сложность времени: O (n) Если мы посмотрим поближе, мы можем заметить, что каждое ребро дерева пересекается не более двух раз. И в худшем случае, такое же количество дополнительных ребер (как дерево ввода) создаются и удаляются.

Ссылки:
www.liacs.nl/~deutz/DS/september28.pdf
www.scss.tcd.ie/disciplines/software_systems/…/HughGibbonsSlides.pdf

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме или хотите поделиться дополнительной информацией о стеке Morris Inorder Tree Traversal.

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

Inorder Tree Traversal без рекурсии и без стека!

0.00 (0%) 0 votes