Рубрики

Обход Морриса для Предзаказа

Деревья

Используя Morris Traversal, мы можем обходить дерево без использования стека и рекурсии. Алгоритм для Preorder почти аналогичен прохождению Морриса для Inorder .

1. .. Если оставленный дочерний элемент равен нулю, выведите данные текущего узла. Переместиться к правому ребенку.
…. Иначе , Сделайте правый потомок предшественника inorder указателем на текущий узел. Возникают два случая:
……… a) Правый дочерний элемент предшествующего предшественника уже указывает на текущий узел. Установите право ребенка в NULL. Переместиться к правому потомку текущего узла.
……… б) Правильный ребенок — NULL. Установите его на текущий узел. Распечатайте данные текущего узла и перейдите к левому потомку текущего узла.
2. .. Итерировать до тех пор, пока текущий узел не станет NULL.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для обхода Morris Preorder
#include <bits/stdc++.h>

using namespace std; 

  

class node 

{ 

    public:

    int data; 

    node *left, *right; 

}; 

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

node* newNode(int data) 

{ 

    node* temp = new node();

    temp->data = data; 

    temp->left = temp->right = NULL; 

    return temp; 

} 

  
// Предзаказ обхода без рекурсии и без стека

void morrisTraversalPreorder(node* root) 

{ 

    while (root) 

    { 

        // Если значение параметра left child равно нулю, вывести данные текущего узла. Переместить в

        // правый ребенок.

        if (root->left == NULL) 

        { 

            cout<<root->data<<" "; 

            root = root->right; 

        } 

        else

        { 

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

            node* current = root->left; 

            while (current->right && current->right != root) 

                current = current->right; 

  

            // Если правый потомок предшествующего предшественника уже указывает на

            // этот узел

            if (current->right == root) 

            { 

                current->right = NULL; 

                root = root->right; 

            } 

  

            // Если правый потомок не указывает на этот узел, то выведите это

            // узел и сделать правильный дочерний элемент указывать на этот узел

            else

            { 

                cout<<root->data<<" "; 

                current->right = root; 

                root = root->left; 

            } 

        } 

    } 

} 

  
// Функция для прохождения предзаказа sStandard

void preorder(node* root) 

{ 

    if (root) 

    { 

        cout<<root->data<<" "; 

        preorder(root->left); 

        preorder(root->right); 

    } 

} 

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

int main() 

{ 

    node* root = NULL; 

  

    root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

  

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

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

  

    root->right->left = newNode(6); 

    root->right->right = newNode(7); 

  

    root->left->left->left = newNode(8); 

    root->left->left->right = newNode(9); 

  

    root->left->right->left = newNode(10); 

    root->left->right->right = newNode(11); 

  

    morrisTraversalPreorder(root); 

  

    cout<<endl; 

    preorder(root); 

  

    return 0; 

} 

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

С

// C программа для обхода Morris Preorder
#include <stdio.h>
#include <stdlib.h>

  

struct node

{

    int data;

    struct node *left, *right;

};

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

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

struct node* newNode(int data)

{

    struct node* temp = (struct node*) malloc(sizeof(struct node));

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Предзаказ обхода без рекурсии и без стека

void morrisTraversalPreorder(struct node* root)

{

    while (root)

    {

        // Если значение параметра left child равно нулю, вывести данные текущего узла. Переместить в

        // правый ребенок.

        if (root->left == NULL)

        {

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

            root = root->right;

        }

        else

        {

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

            struct node* current = root->left;

            while (current->right && current->right != root)

                current = current->right;

  

            // Если правый потомок предшествующего предшественника уже указывает на

            // этот узел

            if (current->right == root)

            {

                current->right = NULL;

                root = root->right;

            }

  

            // Если правый потомок не указывает на этот узел, то выведите это

            // узел и сделать правильный дочерний элемент указывать на этот узел

            else

            {

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

                current->right = root;

                root = root->left;

            }

        }

    }

}

  
// Функция для прохождения предзаказа sStandard

void preorder(struct node* root)

{

    if (root)

    {

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

        preorder(root->left);

        preorder(root->right);

    }

}

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

int main()

{

    struct node* root = NULL;

  

    root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

  

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

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

  

    root->right->left = newNode(6);

    root->right->right = newNode(7);

  

    root->left->left->left = newNode(8);

    root->left->left->right = newNode(9);

  

    root->left->right->left = newNode(10);

    root->left->right->right = newNode(11);

  

    morrisTraversalPreorder(root);

  

    printf("\n");

    preorder(root);

  

    return 0;

}

Джава

// Java-программа для реализации обхода предварительного заказа Морриса

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

class Node {

      

    int data;

    Node left, right;

      

    Node(int item) {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

      

    Node root;

      

    void morrisTraversalPreorder()

    {

        morrisTraversalPreorder(root);

    }

  

    // Предзаказ обхода без рекурсии и без стека

    void morrisTraversalPreorder(Node node) {

        while (node != null) {

  

            // Если значение параметра left child равно нулю, вывести данные текущего узла. Переместить в

            // правый ребенок.

            if (node.left == null) {

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

                node = node.right;

            } else {

  

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

                Node current = node.left;

                while (current.right != null && current.right != node) {

                    current = current.right;

                }

  

                // Если правый потомок по порядку предшественника

                // уже указывает на этот узел

                if (current.right == node) {

                    current.right = null;

                    node = node.right;

                }

   

                // Если правый потомок не указывает на этот узел, то выведите

                // этот узел и сделать правильный дочерний элемент указателем на этот узел

                else {

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

                    current.right = node;

                    node = node.left;

                }

            }

        }

    }

      

    void preorder()

    {

        preorder(root);

    }

  

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

    void preorder(Node node) {

        if (node != null) {

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

            preorder(node.left);

            preorder(node.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.root.right.left = new Node(6);

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

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

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

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

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

        tree.morrisTraversalPreorder();

        System.out.println("");

        tree.preorder();

          

    }

}

  
// этот код предоставлен Mayank Jaiswal

python3

# Python программа для обхода Morris Preorder

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

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Предзаказ обхода без
# рекурсия и без стека

def MorrisTraversal(root):

    curr = root

  

    while curr:

        # Если оставленный дочерний элемент нулевой, выведите

        # данные текущего узла. И обновить

        # текущий указатель на правого потомка.

        if curr.left is None:

            print(curr.data, end= " ")

            curr = curr.right

  

        else:

            # Найти inorder предшественника

            prev = curr.left

  

            while prev.right is not None and prev.right is not curr:

                prev = prev.right

  

            # Если правильный ребенок по порядку

            # предшественник уже указывает на

            # текущий узел, обновите

            # текущий с правильным ребенком

            if prev.right is curr:

                prev.right = None

                curr = curr.right

                  

            # else Если правильный ребенок не указывает

            # к текущему узлу, затем распечатайте это

            # данные узла и обновление правого потомка

            # указатель с текущего узла и обновления

            # текущий с оставленным ребенком

            else:

                print (curr.data, end=" ")

                prev.right = curr 

                curr = curr.left

  
# Функция для прохождения предварительного заказа sStandard

def preorfer(root):

    if root :

        print(root.data, end = " ")

        preorfer(root.left)

        preorfer(root.right)

          

  
# Драйвер программы для тестирования

root = Node(1)

root.left = Node(2)

root.right = Node(3)

  

root.left.left = Node(4)

root.left.right = Node(5)

  

root.right.left= Node(6)

root.right.right = Node(7)

  

root.left.left.left = Node(8)

root.left.left.right = Node(9)

  

root.left.right.left = Node(10)

root.left.right.right = Node(11)

  

  
MorrisTraversal(root)

print("\n")

preorfer(root)

  

  
# Этот код предоставлен 'Aartee'

C #

// C # программа для реализации Morris
// предзаказ обхода

using System;

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  

public virtual void morrisTraversalPreorder()

{

    morrisTraversalPreorder(root);

}

  
// Предзаказ обхода без
// рекурсия и без стека

public virtual void morrisTraversalPreorder(Node node)

{

    while (node != null)

    {

  

        // Если оставленный дочерний элемент нулевой, выведите

        // данные текущего узла. Переместиться к правому ребенку.

        if (node.left == null)

        {

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

            node = node.right;

        }

        else

        {

  

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

            Node current = node.left;

            while (current.right != null && 

                   current.right != node)

            {

                current = current.right;

            }

  

            // Если правый потомок по порядку предшественника

            // уже указывает на этот узел

            if (current.right == node)

            {

                current.right = null;

                node = node.right;

            }

  

            // Если правильный ребенок не указывает на

            // этот узел, затем распечатать этот узел

            // и сделать правильный дочерний элемент указателем на этот узел

            else

            {

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

                current.right = node;

                node = node.left;

            }

        }

    }

}

  

public virtual void preorder()

{

    preorder(root);

}

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

public virtual void preorder(Node node)

{

    if (node != null)

    {

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

        preorder(node.left);

        preorder(node.right);

    }

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    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.root.right.left = new Node(6);

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

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

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

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

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

    tree.morrisTraversalPreorder();

    Console.WriteLine("");

    tree.preorder();

}
}

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


Выход:

1 2 4 8 9 5 10 11 3 6 7
1 2 4 8 9 5 10 11 3 6 7

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

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Обход Морриса для Предзаказа

0.00 (0%) 0 votes