Рубрики

Итеративный обход предзаказа

Для заданного двоичного дерева напишите итеративную функцию для печати обхода предзаказа заданного двоичного дерева.

Направьте это для рекурсивного обхода предзаказа двоичного дерева. Чтобы преобразовать изначально рекурсивные процедуры в итеративные, нам нужен явный стек. Ниже приведен простой итеративный процесс на основе стека для печати обхода Preorder.
1) Создайте пустой стек стека nodeStack и поместите корневой узел в стек.
2) Делайте следующее, пока nodeStack не пуст.
…. а) вытолкнуть предмет из стопки и распечатать его.
…. б) толкнуть правого потомка вытолкнутого предмета в стек
…. в) толкнуть левого потомка вытолкнутого предмета в стек

Правый потомок помещается перед левым потомком, чтобы убедиться, что левое поддерево обрабатывается первым.

C ++

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

  

using namespace std;

  
/ * Узел двоичного дерева имеет данные, левый и правый дочерние элементы * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

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

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

struct node* newNode(int data)

{

    struct node* node = new struct node;

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

}

  
// Итеративный процесс для печати предзаказа обхода двоичного дерева

void iterativePreorder(node *root)

{

    // Базовый вариант

    if (root == NULL)

       return;

  

    // Создаем пустой стек и помещаем в него корень

    stack<node *> nodeStack;

    nodeStack.push(root);

  

    / * Поп все предметы по одному. Следуйте за каждым сованным предметом

       а) распечатай

       б) подтолкнуть своего правого ребенка

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

    Обратите внимание, что правый потомок помещается первым, поэтому левый обрабатывается первым * /

    while (nodeStack.empty() == false)

    {

        // Вытащить верхний элемент из стека и распечатать его

        struct node *node = nodeStack.top();

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

        nodeStack.pop();

  

        // Вставить правый и левый потомки вытолкнутого узла в стек

        if (node->right)

            nodeStack.push(node->right);

        if (node->left)

            nodeStack.push(node->left);

    }

}

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

int main()

{

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

            10

          / /

        8 2

      ///

    3 5 2

  * /

  struct node *root = newNode(10);

  root->left        = newNode(8);

  root->right       = newNode(2);

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

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

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

  iterativePreorder(root);

  return 0;

}

Джава

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

import java.util.Stack;

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int item) {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

  

    Node root;

      

    void iterativePreorder()

    {

        iterativePreorder(root);

    }

  

    // Итеративный процесс для печати предзаказа обхода двоичного дерева

    void iterativePreorder(Node node) {

          

        // Базовый вариант

        if (node == null) {

            return;

        }

  

        // Создаем пустой стек и помещаем в него корень

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

        nodeStack.push(root);

  

        / * Поп все предметы по одному. Следуйте за каждым сованным предметом

         а) распечатай

         б) подтолкнуть своего правого ребенка

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

         Обратите внимание, что правый потомок помещается первым, поэтому левый обрабатывается первым * /

        while (nodeStack.empty() == false) {

              

            // Вытащить верхний элемент из стека и распечатать его

            Node mynode = nodeStack.peek();

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

            nodeStack.pop();

  

            // Вставить правый и левый потомки вытолкнутого узла в стек

            if (mynode.right != null) {

                nodeStack.push(mynode.right);

            }

            if (mynode.left != null) {

                nodeStack.push(mynode.left);

            }

        }

    }

  

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

    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

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

        tree.iterativePreorder();

  

    }

}

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

питон

# Программа Python для выполнения итеративного обхода предварительного заказа

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Итеративный процесс для печати предзаказа путешествия BT

def iterativePreorder(root):

      

    # Базовый вариант

    if root is None:

        return 

  

    # создайте пустой стек и вставьте в него root

    nodeStack = []

    nodeStack.append(root)

  

    # Поп все предметы по одному. Следуйте за каждым сованным предметом

    # а) распечатай

    # б) выдвинь своего правильного ребенка

    # в) толкнуть своего левого ребенка

    # Обратите внимание, что правый потомок толкается первым, так что левый

    # обрабатывается первым * /

    while(len(nodeStack) > 0):

          

        # Вытащите верхний элемент из стека и распечатайте его

        node = nodeStack.pop()

        print node.data,

          

        # Нажмите правую и левую дочерние элементы вытолкнутого узла

        # укладывать

        if node.right is not None:

            nodeStack.append(node.right)

        if node.left is not None:

            nodeStack.append(node.left)

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

root = Node(10)

root.left = Node(8)

root.right = Node(2)

root.left.left = Node(3)

root.left.right = Node(5)

root.right.left = Node(2)

iterativePreorder(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;

    }

}

  

class GFG

{

public Node root;

  

public virtual void iterativePreorder()

{

    iterativePreorder(root);

}

  
// Итерационный процесс для печати предзаказа
// обход двоичного дерева

public virtual void iterativePreorder(Node node)

{

  

    // Базовый вариант

    if (node == null)

    {

        return;

    }

  

    // Создаем пустой стек и помещаем в него корень

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

    nodeStack.Push(root);

  

    / * Поп все предметы по одному. Делать следующее

       за каждый всплывающий предмет

    а) распечатай

    б) подтолкнуть своего правого ребенка

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

    Обратите внимание, что правый ребенок толкается первым, так

    то, что осталось обработано первым * /

    while (nodeStack.Count > 0)

    {

  

        // Вытащить верхний элемент из стека и распечатать его

        Node mynode = nodeStack.Peek();

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

        nodeStack.Pop();

  

        // толкаем правого и левого детей

        // вытолкнутый узел в стек

        if (mynode.right != null)

        {

            nodeStack.Push(mynode.right);

        }

        if (mynode.left != null)

        {

            nodeStack.Push(mynode.left);

        }

    }

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    tree.root = new Node(10);

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

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

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

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

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

    tree.iterativePreorder();

}
}

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

Выход:

10 8 3 5 2 2

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

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

Итеративный обход предзаказа

0.00 (0%) 0 votes