Рубрики

Порядок бинарного обхода дерева без резьбы без рекурсии или стека

Мы обсудили основанный на Нити Моррис Траверсал . Можем ли мы выполнить обход по порядку без потоков, если нам доступны родительские указатели?

Input: Root of Below Tree [Every node of 
       tree has parent pointer also]
        10
      /    \
     5     100
           /  \
          80  120 
Output: 5 10 80 100 120
The code should not extra space (No Recursion
and stack)

При прохождении по порядку мы следуем «левый корень вправо». Мы можем перейти к детям, используя левый и правый указатели. Когда узел посещен, нам также нужно перейти к родителю. Например, в приведенном выше дереве нам нужно перейти к 10 после печати 5. Для этого мы используем указатель родителя. Ниже приведен алгоритм.

1. Initialize current node as root
2. Initialize a flag: leftdone = false;
3. Do following while root is not NULL
     a) If leftdone is false, set current node as leftmost
        child of node. 
     b) Mark leftdone as true and print current node.
     c) If right child of current nodes exists, set current
        as right child and set leftdone as false.
     d) Else If parent exists, If current node is left child
        of its parent, set current node as parent. 
        If current node is right child, keep moving to ancestors
        using parent pointer while current node is right child
        of its parent.  
     e) Else break (We have reached back to root)

Иллюстрация:

Let us consider below tree for illustration.
        10
      /    \
     5     100
           /  \
          80  120 

Initialize: Current node = 10, leftdone = false

Since leftdone is false, we move to 5 (3.a), print it
and set leftdone = true.

Now we move to parent of 5 (3.d). Node 10 is 
printed because leftdone is true.

We move to right of 10 and set leftdone as false (3.c)

Now current node is 100. Since leftdone is false, we move
to 80 (3.a) and set leftdone as true.  We print current 
node 80 and move back to parent 100 (3.d).  Since leftdone
is true, we print current node 100. 

Right of 100 exists, so we move to 120 (3.c).   We print
current node 120.

Since 120 is right child of its parent we keep moving to parent
while parent is right child of its parent.  We reach root. So
we break the loop and stop

Ниже приведена реализация вышеуказанного алгоритма. Обратите внимание, что реализация использует двоичное дерево поиска вместо двоичного дерева. Мы также можем использовать ту же функцию inorder () для двоичного дерева. Причина использования бинарного дерева поиска в приведенном ниже коде состоит в том, что легко построить бинарное дерево поиска с родительскими указателями и легко проверить результат (в BST обход сортировки всегда сортируется).

C ++

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

using namespace std;

  
// BST Node

struct Node

{

    Node *left, *right, *parent;

    int key;

};

  
// Вспомогательная функция для создания нового узла BST

Node *newNode(int item)

{

    Node *temp = new Node;

    temp->key = item;

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

    return temp;

}

  
/ * Утилита для вставки нового узла с

   данный ключ в BST * /

Node *insert(Node *node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL) return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

    {

        node->left  = insert(node->left, key);

        node->left->parent = node;

    }

    else if (key > node->key)

    {

        node->right = insert(node->right, key);

        node->right->parent = node;

    }

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Функция для печати обхода inorder с использованием parent
// указатель

void inorder(Node *root)

{

    bool leftdone = false;

  

    // Начать обход из корня

    while (root)

    {

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

        // самый левый ребенок

        if (!leftdone)

        {

            while (root->left)

                root = root->left;

        }

  

        // Распечатать данные root

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

  

        // Отметить как выполнено

        leftdone = true;

  

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

        if (root->right)

        {

            leftdone = false;

            root = root->right;

        }

  

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

        else if (root->parent)

        {

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

            // сначала заходим к родителю родителя

            while (root->parent &&

                   root == root->parent->right)

                root = root->parent;

            if (!root->parent)

                break;

            root = root->parent;

        }

        else break;

    }

}

  

int main(void)

{

    Node * root = NULL;

  

    root = insert(root, 24);

    root = insert(root, 27);

    root = insert(root, 29);

    root = insert(root, 34);

    root = insert(root, 14);

    root = insert(root, 4);

    root = insert(root, 10);

    root = insert(root, 22);

    root = insert(root, 13);

    root = insert(root, 3);

    root = insert(root, 2);

    root = insert(root, 6);

  

    printf("Inorder traversal is \n");

    inorder(root);

  

    return 0;

}

Джава

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

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

   
// BST узел

class Node 

{

    int key;

    Node left, right, parent;

   

    public Node(int key) 

    {

        this.key = key;

        left = right = parent = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Утилита для вставки нового узла с

       данный ключ в BST * /

    Node insert(Node node, int key) 

    {

        / * Если дерево пустое, вернуть новый узел * /

        if (node == null

            return new Node(key);

   

        / * В противном случае вернемся вниз по дереву * /

        if (key < node.key) 

        {

            node.left = insert(node.left, key);

            node.left.parent = node;

        

        else if (key > node.key) 

        {

            node.right = insert(node.right, key);

            node.right.parent = node;

        }

           

        / * вернуть (неизмененный) указатель узла * /

        return node;

    }

   

    // Функция для печати обхода inorder с использованием parent

    // указатель

    void inorder(Node root) 

    {

        boolean leftdone = false;

   

        // Начать обход из корня

        while (root != null

        {

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

            // самый левый ребенок

            if (!leftdone) 

            {

                while (root.left != null

                {

                    root = root.left;

                }

            }

   

            // Распечатать данные root

            System.out.print(root.key + " ");

   

            // Отметить как выполнено

            leftdone = true;

   

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

            if (root.right != null

            {

                leftdone = false;

                root = root.right;

            

               

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

            else if (root.parent != null

            {

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

                // сначала заходим к родителю родителя

                while (root.parent != null

                        && root == root.parent.right) 

                    root = root.parent;

                   

                if (root.parent == null

                    break;

                root = root.parent;

            

            else

                break;

        }

    }

   

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = tree.insert(tree.root, 24);

        tree.root = tree.insert(tree.root, 27);

        tree.root = tree.insert(tree.root, 29);

        tree.root = tree.insert(tree.root, 34);

        tree.root = tree.insert(tree.root, 14);

        tree.root = tree.insert(tree.root, 4);

        tree.root = tree.insert(tree.root, 10);

        tree.root = tree.insert(tree.root, 22);

        tree.root = tree.insert(tree.root, 13);

        tree.root = tree.insert(tree.root, 3);

        tree.root = tree.insert(tree.root, 2);

        tree.root = tree.insert(tree.root, 6);

   

        System.out.println("Inorder traversal is ");

        tree.inorder(tree.root);

    }

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

python3

# Программа Python3 для печати обхода по порядку
# Двоичное дерево поиска (BST) без рекурсии и стека

  
# Сервисная функция для создания нового узла BST

class newNode:

    def __init__(self, item):

        self.key = item 

        self.parent = self.left = self.right = None

      
# Полезная функция для вставки нового
# узел с данным ключом в BST

def insert(node, key):

      

    # Если дерево пусто, вернуть новый узел

    if node == None:

        return newNode(key) 

  

    # В противном случае, повторить вниз по дереву

    if key < node.key:

        node.left = insert(node.left, key) 

        node.left.parent = node

    elif key > node.key:

        node.right = insert(node.right, key) 

        node.right.parent = node

  

    # вернуть (неизмененный) указатель узла

    return node

  
# Функция для печати обхода заказа
# используя родительский указатель

def inorder(root):

    leftdone = False

  

    # Начать обход из корня

    while root:

          

        # Если левый ребенок не пройден,

        # найти самого левого ребенка

        if leftdone == False:

            while root.left:

                root = root.left

  

        # Распечатать данные root

        print(root.key, end = " "

  

        # Отметить как выполненное

        leftdone = True

  

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

        if root.right:

            leftdone = False

            root = root.right

  

        # Если нужного ребенка не существует, перейдите к родителю

        elif root.parent:

              

            # Если этот узел является правым потомком его

            # parent, сначала зайти к родителю parent

            while root.parent and root == root.parent.right: 

                root = root.parent 

            if root.parent == None:

                break

            root = root.parent

        else:

            break

              
Код водителя

if __name__ == '__main__':

    root = None

  

    root = insert(root, 24

    root = insert(root, 27

    root = insert(root, 29

    root = insert(root, 34

    root = insert(root, 14

    root = insert(root, 4

    root = insert(root, 10

    root = insert(root, 22

    root = insert(root, 13

    root = insert(root, 3

    root = insert(root, 2

    root = insert(root, 6

  

    print("Inorder traversal is "

    inorder(root) 

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

C #

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

using System;

  
// BST узел

class Node 

{

    public int key;

    public Node left, right, parent;

  

    public Node(int key) 

    {

        this.key = key;

        left = right = parent = null;

    }

}

  

class BinaryTree 

{
Node root;

  
/ * Утилита для вставки
новый узел с данным ключом в BST * /

Node insert(Node node, int key) 

{

    / * Если дерево пусто,

       вернуть новый узел * /

    if (node == null

        return new Node(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key) 

    {

        node.left = insert(node.left, key);

        node.left.parent = node;

    

    else if (key > node.key) 

    {

        node.right = insert(node.right, key);

        node.right.parent = node;

    }

      

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

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

void inorder(Node root) 

{

    Boolean leftdone = false;

  

    // Начать обход из корня

    while (root != null

    {

        // Если левый ребенок не пройден,

        // найти самого левого потомка

        if (!leftdone) 

        {

            while (root.left != null

            {

                root = root.left;

            }

        }

  

        // Распечатать данные root

        Console.Write(root.key + " ");

  

        // Отметить как выполнено

        leftdone = true;

  

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

        if (root.right != null

        {

            leftdone = false;

            root = root.right;

        

          

        // Если правильного ребенка не существует,

        // перейти к родителю

        else if (root.parent != null

        {

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

            // его родителя, посещение родителя

            // родитель первым

            while (root.parent != null && 

                   root == root.parent.right) 

                root = root.parent;

              

            if (root.parent == null

                break;

            root = root.parent;

        

        else

            break;

    }

}

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

static public void Main(String[] args) 

{

    BinaryTree tree = new BinaryTree();

    tree.root = tree.insert(tree.root, 24);

    tree.root = tree.insert(tree.root, 27);

    tree.root = tree.insert(tree.root, 29);

    tree.root = tree.insert(tree.root, 34);

    tree.root = tree.insert(tree.root, 14);

    tree.root = tree.insert(tree.root, 4);

    tree.root = tree.insert(tree.root, 10);

    tree.root = tree.insert(tree.root, 22);

    tree.root = tree.insert(tree.root, 13);

    tree.root = tree.insert(tree.root, 3);

    tree.root = tree.insert(tree.root, 2);

    tree.root = tree.insert(tree.root, 6);

  

    Console.WriteLine("Inorder traversal is ");

    tree.inorder(tree.root);

}
}

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

Выход:

Inorder traversal is 
2 3 4 6 10 13 14 22 24 27 29 34

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

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

Порядок бинарного обхода дерева без резьбы без рекурсии или стека

0.00 (0%) 0 votes