Рубрики

Построить BST из заданного обхода предзаказа | Набор 2

По заданному обходу бинарного дерева поиска построим BST.

Например, если заданный обход равен {10, 5, 1, 7, 40, 50}, то выходные данные должны быть корнем следующего дерева.

     10
   /   \
  5     40
 /  \      \
1    7      50  

Мы обсуждали O (n ^ 2) и O (n) рекурсивные решения в предыдущем посте . Ниже приводится итеративное решение на основе стека, которое работает за O (n).

1. Создайте пустой стек.

2. Сделать первое значение как root. Вставьте его в стек.

3. Продолжайте выталкивать, пока стек не пуст и следующее значение больше верхнего значения стека. Сделайте это значение правым потомком последнего подключенного узла. Вставьте новый узел в стек.

4. Если следующее значение меньше верхнего значения стека, сделайте это значение левым потомком верхнего узла стека. Вставьте новый узел в стек.

5. Повторяйте шаги 2 и 3, пока в pre [] не останутся элементы.

C ++

// AO (n) итерационная программа для построения BST из обхода предзаказа
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node *left, *right; 

} node; 

  
// У стека есть массив узлов, емкости и вершины

class Stack 

    public:

    int top; 

    int capacity; 

    Node** array; 

} stack; 

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

Node* newNode( int data ) 

    Node* temp = new Node(); 

    temp->data = data; 

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

    return temp; 

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

Stack* createStack( int capacity ) 

    Stack* stack = new Stack(); 

    stack->top = -1; 

    stack->capacity = capacity; 

    stack->array = new Node*[stack->capacity * sizeof( Node* )]; 

    return stack; 

  
// Утилита для проверки заполнения стека

int isFull( Stack* stack ) 

    return stack->top == stack->capacity - 1; 

  
// Утилита для проверки, если стек пуст

int isEmpty( Stack* stack ) 

    return stack->top == -1; 

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

void push( Stack* stack, Node* item ) 

    if( isFull( stack ) ) 

        return

    stack->array[ ++stack->top ] = item; 

  
// Утилита для удаления элемента из стека
Node* pop( Stack* stack ) 

    if( isEmpty( stack ) ) 

        return NULL; 

    return stack->array[ stack->top-- ]; 

  
// Вспомогательная функция для получения верхнего узла стека
Node* peek( Stack* stack ) 

    return stack->array[ stack->top ]; 

  
// Основная функция, которая создает BST из pre []

Node* constructTree ( int pre[], int size ) 

    // Создание стека емкости, равной размеру

    Stack* stack = createStack( size ); 

  

    // Первый элемент pre [] всегда root

    Node* root = newNode( pre[0] ); 

  

    // Push root

    push( stack, root ); 

  

    int i; 

    Node* temp; 

  

    // Итерация по остальным элементам размера 1 данного массива предварительного заказа

    for ( i = 1; i < size; ++i ) 

    

        temp = NULL; 

  

        / * Продолжать выскакивать, пока следующее значение больше

        верхнее значение стека. * /

        while ( !isEmpty( stack ) && pre[i] > peek( stack )->data ) 

            temp = pop( stack ); 

  

        // Сделать это большее значение как правильный ребенок

                // и помещаем его в стек

        if ( temp != NULL) 

        

            temp->right = newNode( pre[i] ); 

            push( stack, temp->right ); 

        

  

        // Если следующее значение меньше вершины стека

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

                // верхний узел стека. Вставить новый узел в стек

        else

        

            peek( stack )->left = newNode( pre[i] ); 

            push( stack, peek( stack )->left ); 

        

    

  

    return root; 

  

  
// Полезная функция для печати обхода по порядку двоичного дерева

void printInorder (Node* node) 

    if (node == NULL) 

        return

    printInorder(node->left); 

    cout<<node->data<<" "

    printInorder(node->right); 

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

int main () 

    int pre[] = {10, 5, 1, 7, 40, 50}; 

    int size = sizeof( pre ) / sizeof( pre[0] ); 

  

    Node *root = constructTree(pre, size); 

  

    cout<<"Inorder traversal of the constructed tree: \n"

    printInorder(root); 

  

    return 0; 

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

С

// AO (n) итерационная программа для построения BST из обхода предзаказа
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

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

typedef struct Node

{

    int data;

    struct Node *left, *right;

} Node;

  
// У стека есть массив узлов, емкости и вершины

typedef struct Stack

{

    int top;

    int capacity;

    Node* *array;

} Stack;

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

Node* newNode( int data )

{

    Node* temp = (Node *)malloc( sizeof( Node ) );

    temp->data = data;

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

    return temp;

}

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

Stack* createStack( int capacity )

{

    Stack* stack = (Stack *)malloc( sizeof( Stack ) );

    stack->top = -1;

    stack->capacity = capacity;

    stack->array = (Node **)malloc( stack->capacity * sizeof( Node* ) );

    return stack;

}

  
// Утилита для проверки заполнения стека

int isFull( Stack* stack )

{

    return stack->top == stack->capacity - 1;

}

  
// Утилита для проверки, если стек пуст

int isEmpty( Stack* stack )

{

    return stack->top == -1;

}

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

void push( Stack* stack, Node* item )

{

    if( isFull( stack ) )

        return;

    stack->array[ ++stack->top ] = item;

}

  
// Утилита для удаления элемента из стека
Node* pop( Stack* stack )
{

    if( isEmpty( stack ) )

        return NULL;

    return stack->array[ stack->top-- ];

}

  
// Вспомогательная функция для получения верхнего узла стека
Node* peek( Stack* stack )
{

    return stack->array[ stack->top ];

}

  
// Основная функция, которая создает BST из pre []

Node* constructTree ( int pre[], int size )

{

    // Создание стека емкости, равной размеру

    Stack* stack = createStack( size );

  

    // Первый элемент pre [] всегда root

    Node* root = newNode( pre[0] );

  

    // Push root

    push( stack, root );

  

    int i;

    Node* temp;

  

    // Итерация по остальным элементам размера 1 данного массива предварительного заказа

    for ( i = 1; i < size; ++i )

    {

        temp = NULL;

  

        / * Продолжать выскакивать, пока следующее значение больше

           верхнее значение стека. * /

        while ( !isEmpty( stack ) && pre[i] > peek( stack )->data )

            temp = pop( stack );

  

        // Сделать это большее значение как правильный ребенок

        // и помещаем его в стек

        if ( temp != NULL)

        {

            temp->right = newNode( pre[i] );

            push( stack, temp->right );

        }

  

        // Если следующее значение меньше вершины стека

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

        // верхний узел стека. Вставить новый узел в стек

        else

        {

            peek( stack )->left = newNode( pre[i] );

            push( stack, peek( stack )->left );

        }

    }

  

    return root;

}

  

  
// Полезная функция для печати обхода по порядку двоичного дерева

void printInorder (Node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

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

    printInorder(node->right);

}

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

int main ()

{

    int pre[] = {10, 5, 1, 7, 40, 50};

    int size = sizeof( pre ) / sizeof( pre[0] );

  

    Node *root = constructTree(pre, size);

  

    printf("Inorder traversal of the constructed tree: \n");

    printInorder(root);

  

    return 0;

}

Джава

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

  

import java.util.*;

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class BinaryTree {

  

    // Основная функция, которая создает BST из pre []

    Node constructTree(int pre[], int size) {

  

        // Первый элемент pre [] всегда root

        Node root = new Node(pre[0]);

  

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

  

        // Push root

        s.push(root);

  

        // Итерация по остальным элементам размера 1 данного массива предварительного заказа

        for (int i = 1; i < size; ++i) {

            Node temp = null;

  

            / * Продолжать выскакивать, пока следующее значение больше

             верхнее значение стека. * /

            while (!s.isEmpty() && pre[i] > s.peek().data) {

                temp = s.pop();

            }

  

            // Сделать это большее значение как правильный ребенок

            // и помещаем его в стек

            if (temp != null) {

                temp.right = new Node(pre[i]);

                s.push(temp.right);

            

              

            // Если следующее значение меньше вершины стека

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

            // верхний узел стека. Вставить новый узел в стек

            else {

                temp = s.peek();

                temp.left = new Node(pre[i]);

                s.push(temp.left);

            }

        }

  

        return root;

    }

  

    // Полезная функция для печати обхода по порядку двоичного дерева

    void printInorder(Node node) {

        if (node == null) {

            return;

        }

        printInorder(node.left);

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

        printInorder(node.right);

    }

  

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

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        int pre[] = new int[]{10, 5, 1, 7, 40, 50};

        int size = pre.length;

        Node root = tree.constructTree(pre, size);

        System.out.println("Inorder traversal of the constructed tree is ");

        tree.printInorder(root);

    }

}

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

C #

using System;

using System.Collections.Generic;

  
// c # программа для построения BST из заданного обхода предварительного заказа

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

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinaryTree

{

  

    // Основная функция, которая создает BST из pre []

    public virtual Node constructTree(int[] pre, int size)

    {

  

        // Первый элемент pre [] всегда root

        Node root = new Node(pre[0]);

  

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

  

        // Push root

        s.Push(root);

  

        // Итерация по остальным элементам размера 1 данного массива предварительного заказа

        for (int i = 1; i < size; ++i)

        {

            Node temp = null;

  

            / * Продолжать выскакивать, пока следующее значение больше

             верхнее значение стека. * /

            while (s.Count > 0 && pre[i] > s.Peek().data)

            {

                temp = s.Pop();

            }

  

            // Сделать это большее значение как правильный ребенок

            // и помещаем его в стек

            if (temp != null)

            {

                temp.right = new Node(pre[i]);

                s.Push(temp.right);

            }

  

            // Если следующее значение меньше вершины стека

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

            // верхний узел стека. Вставить новый узел в стек

            else

            {

                temp = s.Peek();

                temp.left = new Node(pre[i]);

                s.Push(temp.left);

            }

        }

  

        return root;

    }

  

    // Полезная функция для печати обхода по порядку двоичного дерева

    public virtual void printInorder(Node node)

    {

        if (node == null)

        {

            return;

        }

        printInorder(node.left);

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

        printInorder(node.right);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        int[] pre = new int[]{10, 5, 1, 7, 40, 50};

        int size = pre.Length;

        Node root = tree.constructTree(pre, size);

        Console.WriteLine("Inorder traversal of the constructed tree is ");

        tree.printInorder(root);

    }

}

  

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

Выход:

Inorder traversal of the constructed tree is 
1 5 7 10 40 50  

Сложность времени: O (n). Сложность выглядит больше с первого взгляда. Если мы присмотримся поближе, то увидим, что каждый предмет толкается и высовывается только один раз. Таким образом, максимум 2n операций push / pop выполняются в основных циклах constructTree (). Следовательно, временная сложность составляет O (n).

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

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

Построить BST из заданного обхода предзаказа | Набор 2

0.00 (0%) 0 votes