Рубрики

Построить дерево из заданных обходов Inorder и Preorder

Давайте рассмотрим следующие обходы:

Последовательность заказа: DBEAFC
Последовательность предварительного заказа: ABDECF

В последовательности Preorder самый левый элемент является корнем дерева. Итак, мы знаем, что «A» является корнем для заданных последовательностей. Поиск «A» в последовательности Inorder позволяет определить, что все элементы в левой части «A» находятся в левом поддереве, а элементы справа — в правом поддереве. Итак, теперь мы знаем структуру ниже.

                 A
               /   \
             /       \
           D B E     F C

Мы рекурсивно выполняем описанные выше шаги и получаем следующее дерево.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F

Алгоритм: buildTree ()
1) Выберите элемент из Предзаказа. Увеличьте переменную индекса предварительного заказа (preIndex в приведенном ниже коде), чтобы выбрать следующий элемент в следующем рекурсивном вызове.
2) Создайте новый узел дерева tNode с данными в качестве выбранного элемента.
3) Найти индекс выбранного элемента в Inorder. Пусть индекс будет inIndex.
4) Вызовите buildTree для элементов перед inIndex и сделайте построенное дерево левым поддеревом tNode.
5) Вызвать buildTree для элементов после inIndex и сделать построенное дерево правым поддеревом tNode.
6) вернуть tNode.

Спасибо Рохини и Тушару за предложение кода.

C ++

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

using namespace std;

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

class node 

    public:

    char data; 

    node* left; 

    node* right; 

}; 

  
/ * Прототипы для служебных функций * /

int search(char arr[], int strt, int end, char value); 

node* newNode(char data); 

  
/ * Рекурсивная функция для построения двоичного
размера len из обхода Inorder в []
и предварительный обход pre []. Начальные значения
inStrt и inEnd должны быть 0 и len -1.
Функция не проверяет ошибки
для случаев, когда заказ и предварительный заказ не
сформировать дерево * /

node* buildTree(char in[], char pre[], int inStrt, int inEnd) 

    static int preIndex = 0; 

  

    if (inStrt > inEnd) 

        return NULL; 

  

    / * Выбрать текущий узел из предзаказа

    обход с использованием preIndex

    и увеличиваем preIndex * /

    node* tNode = newNode(pre[preIndex++]); 

  

    / * Если у этого узла нет потомков, вернуть * /

    if (inStrt == inEnd) 

        return tNode; 

  

    / * Иначе найти индекс этого узла в обходе Inorder * /

    int inIndex = search(in, inStrt, inEnd, tNode->data); 

  

    / * Используя индекс в обходе Inorder, создайте left и

    правый субтресс * /

    tNode->left = buildTree(in, pre, inStrt, inIndex - 1); 

    tNode->right = buildTree(in, pre, inIndex + 1, inEnd); 

  

    return tNode; 

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для поиска индекса значения в arr [start ... end]
Функция предполагает, что значение присутствует в в [] * /

int search(char arr[], int strt, int end, char value) 

    int i; 

    for (i = strt; i <= end; i++) 

    

        if (arr[i] == value) 

            return i; 

    

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

node* newNode(char data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

  

    return (Node); 

  
/ * Этот функционал здесь только для проверки buildTree () * /

void printInorder(node* node) 

    if (node == NULL) 

        return

  

    / * первый рецидив на левом ребенке * /

    printInorder(node->left); 

  

    / * затем распечатать данные узла * /

    cout<<node->data<<" "

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder(node->right); 

  
/ * Код водителя * /

int main() 

    char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' }; 

    char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' }; 

    int len = sizeof(in) / sizeof(in[0]); 

    node* root = buildTree(in, pre, 0, len - 1); 

  

    / * Давайте проверим построенное дерево

    печать Insorder обхода * /

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

    printInorder(root); 

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

С

/ * программа для построения дерева с использованием обхода по порядку и по предзаказу * /
#include <stdio.h>
#include <stdlib.h>

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

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

struct node {

    char data;

    struct node* left;

    struct node* right;

};

  
/ * Прототипы для служебных функций * /

int search(char arr[], int strt, int end, char value);

struct node* newNode(char data);

  
/ * Рекурсивная функция для построения двоичного файла размера len из

   Обход по порядку в [] и обход по предзаказу до []. Начальные значения

   inStrt и inEnd должны быть 0 и len -1. Функция не

   сделать любую проверку ошибок для случаев, когда заказ и предварительный заказ

   не формировать дерево * /

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)

{

    static int preIndex = 0;

  

    if (inStrt > inEnd)

        return NULL;

  

    / * Выбрать текущий узел из предзаказа, используя preIndex

    и увеличиваем preIndex * /

    struct node* tNode = newNode(pre[preIndex++]);

  

    / * Если у этого узла нет потомков, вернуть * /

    if (inStrt == inEnd)

        return tNode;

  

    / * Иначе найти индекс этого узла в обходе Inorder * /

    int inIndex = search(in, inStrt, inEnd, tNode->data);

  

    / * Используя индекс в обходе Inorder, создайте left и

     правый субтресс * /

    tNode->left = buildTree(in, pre, inStrt, inIndex - 1);

    tNode->right = buildTree(in, pre, inIndex + 1, inEnd);

  

    return tNode;

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для поиска индекса значения в arr [start ... end]

   Функция предполагает, что значение присутствует в в [] * /

int search(char arr[], int strt, int end, char value)

{

    int i;

    for (i = strt; i <= end; i++) {

        if (arr[i] == value)

            return i;

    }

}

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

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

struct node* newNode(char data)

{

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

    node->data = data;

    node->left = NULL;

    node->right = NULL;

  

    return (node);

}

  
/ * Этот функционал здесь только для проверки buildTree () * /

void printInorder(struct node* node)

{

    if (node == NULL)

        return;

  

    / * первый рецидив на левом ребенке * /

    printInorder(node->left);

  

    / * затем распечатать данные узла * /

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

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder(node->right);

}

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

int main()

{

    char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' };

    char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' };

    int len = sizeof(in) / sizeof(in[0]);

    struct node* root = buildTree(in, pre, 0, len - 1);

  

    / * Давайте проверим построенное дерево, напечатав обход Insorder * /

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

    printInorder(root);

    getchar();

}

Джава

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

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

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

class Node {

    char data;

    Node left, right;

  

    Node(char item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

    Node root;

    static int preIndex = 0;

  

    / * Рекурсивная функция для построения двоичного файла размера len из

       Обход по порядку в [] и обход по предзаказу до [].

       Начальные значения inStrt и inEnd должны быть 0 и len -1.

       Функция не выполняет проверку ошибок в случаях, когда

       порядок и порядок не образуют дерево * /

    Node buildTree(char in[], char pre[], int inStrt, int inEnd)

    {

        if (inStrt > inEnd)

            return null;

  

        / * Выбрать текущий узел из предзаказа, используя preIndex

           и увеличиваем preIndex * /

        Node tNode = new Node(pre[preIndex++]);

  

        / * Если у этого узла нет потомков, вернуть * /

        if (inStrt == inEnd)

            return tNode;

  

        / * Иначе найти индекс этого узла в обходе Inorder * /

        int inIndex = search(in, inStrt, inEnd, tNode.data);

  

        / * Используя индекс в обходе Inorder, создайте left и

           правый субтресс * /

        tNode.left = buildTree(in, pre, inStrt, inIndex - 1);

        tNode.right = buildTree(in, pre, inIndex + 1, inEnd);

  

        return tNode;

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

  

    / * Функция для поиска индекса значения в arr [start ... end]

     Функция предполагает, что значение присутствует в в [] * /

    int search(char arr[], int strt, int end, char value)

    {

        int i;

        for (i = strt; i <= end; i++) {

            if (arr[i] == value)

                return i;

        }

        return i;

    }

  

    / * Этот функционал здесь только для проверки buildTree () * /

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

        char in[] = new char[] { 'D', 'B', 'E', 'A', 'F', 'C' };

        char pre[] = new char[] { 'A', 'B', 'D', 'E', 'C', 'F' };

        int len = in.length;

        Node root = tree.buildTree(in, pre, 0, len - 1);

  

        // построение дерева путем печати обхода заказа

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

        tree.printInorder(root);

    }

}

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

питон

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

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

class Node:

      

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
"" "Рекурсивная функция для построения двоичного файла размера len из

   Обход по порядку в [] и обход по предзаказу до []. Начальные значения

   inStrt и inEnd должны быть 0 и len -1. Функция не

   сделать любую проверку ошибок для случаев, когда заказ и предварительный заказ

   не образуйте дерево "" "

def buildTree(inOrder, preOrder, inStrt, inEnd):

      

    if (inStrt > inEnd):

        return None

  

    # Pich текущий узел из прохождения предзаказа, используя

    # preIndex и приращение preIndex

    tNode = Node(preOrder[buildTree.preIndex])

    buildTree.preIndex += 1

  

    # Если у этого узла нет потомков, вернуть

    if inStrt == inEnd :

        return tNode

  

    # Иначе найти индекс этого узла в обходе Inorder

    inIndex = search(inOrder, inStrt, inEnd, tNode.data)

      

    # Используя индекс в Inorder Traversal, построить слева

    # и правильные поддеревья

    tNode.left = buildTree(inOrder, preOrder, inStrt, inIndex-1)

    tNode.right = buildTree(inOrder, preOrder, inIndex + 1, inEnd)

  

    return tNode

  
# ПОЛЕЗНЫЕ ФУНКЦИИ
# Функция для поиска индекса vaue в arr [start ... end]
# Функция предполагает, что значение присутствует в inOrder []

  

def search(arr, start, end, value):

    for i in range(start, end + 1):

        if arr[i] == value:

            return i

  

def printInorder(node):

    if node is None:

        return 

      

    # первый рецидив на левом ребенке

    printInorder(node.left)

      

    # затем распечатать данные узла

    print node.data,

  

    # теперь возвращаемся на нужного ребенка

    printInorder(node.right)

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

inOrder = ['D', 'B', 'E', 'A', 'F', 'C']

preOrder = ['A', 'B', 'D', 'E', 'C', 'F']

# Статическая переменная preIndex

buildTree.preIndex = 0

root = buildTree(inOrder, preOrder, 0, len(inOrder)-1)

  
# Давайте проверим дерево сборки, напечатав обход Inorder

print "Inorder traversal of the constructed tree is"

printInorder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

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

public class Node {

    public char data;

    public Node left, right;

  

    public Node(char item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG {

    public Node root;

    public static int preIndex = 0;

  

    / * Рекурсивная функция для построения двоичного

размера len из обхода Inorder в []
и предварительный обход pre []. Начальные значения
inStrt и inEnd должны быть 0 и len -1.
Функция не выполняет проверку ошибок для
случаи, когда порядок и порядок не образуют дерево * /

    public virtual Node buildTree(char[] arr, char[] pre,

                                  int inStrt, int inEnd)

    {

        if (inStrt > inEnd) {

            return null;

        }

  

        / * Выбрать текущий узел из предзаказа

     используя preIndex и увеличиваем preIndex * /

        Node tNode = new Node(pre[preIndex++]);

  

        / * Если у этого узла нет потомков, вернуть * /

        if (inStrt == inEnd) {

            return tNode;

        }

  

        / * Остальное найти индекс этого

       узел в обходе Inorder * /

        int inIndex = search(arr, inStrt,

                             inEnd, tNode.data);

  

        / * Использование индекса в обходе Inorder,

    построить левый и правый субтресс * /

        tNode.left = buildTree(arr, pre, inStrt, inIndex - 1);

        tNode.right = buildTree(arr, pre, inIndex + 1, inEnd);

  

        return tNode;

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

  

    / * Функция для поиска индекса значения в arr [start ... end]

Функция предполагает, что значение присутствует в в [] * /

    public virtual int search(char[] arr, int strt,

                              int end, char value)

    {

        int i;

        for (i = strt; i <= end; i++) {

            if (arr[i] == value) {

                return i;

            }

        }

        return i;

    }

  

    / * Этот функционал здесь только для проверки buildTree () * /

    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)

    {

        GFG tree = new GFG();

        char[] arr = new char[] { 'D', 'B', 'E', 'A', 'F', 'C' };

        char[] pre = new char[] { 'A', 'B', 'D', 'E', 'C', 'F' };

        int len = arr.Length;

        Node root = tree.buildTree(arr, pre, 0, len - 1);

  

        // построение дерева путем печати обхода заказа

        Console.WriteLine("Inorder traversal of "

                          + "constructed tree is : ");

        tree.printInorder(root);

    }

}

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

Выход:

Inorder traversal of the constructed tree is 
D B E A F C

Сложность времени: O (n ^ 2). В худшем случае происходит, когда дерево остается перекошенным. Пример обхода предзаказа и обхода для наихудшего случая: {A, B, C, D} и {D, C, B, A}.

Эффективный подход:
Мы можем оптимизировать вышеупомянутое решение, используя хеширование (unordered_map в C ++ или HashMap в Java). Мы храним индексы прохождения порядка в хеш-таблице. Так что поиск может быть выполнен O (1) раз.

C ++

/ * C ++ программа для построения дерева с использованием inorder

   и предварительный обход * /

#include <bits/stdc++.h>

using namespace std;

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

struct Node {

    char data;

    struct Node* left;

    struct Node* right;

};

  

struct Node* newNode(char data)

{

    struct Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

  
/ * Рекурсивная функция для создания двоичного файла размера
len из обхода Inorder в [] и обхода Preorder
предварительно []. Начальные значения inStrt и inEnd должны быть
0 и лен -1. Функция не делает никаких ошибок
проверка случаев, когда заказ и предварительный заказ
не формировать дерево * /

struct Node* buildTree(char in[], char pre[], int inStrt,

                       int inEnd, unordered_map<char, int>& mp)

{

    static int preIndex = 0;

  

    if (inStrt > inEnd)

        return NULL;

  

    / * Выбрать текущий узел из предзаказа, используя preIndex

    и увеличиваем preIndex * /

    char curr = pre[preIndex++];

    struct Node* tNode = newNode(curr);

  

    / * Если у этого узла нет потомков, вернуть * /

    if (inStrt == inEnd)

        return tNode;

  

    / * Иначе найти индекс этого узла в обходе Inorder * /

    int inIndex = mp[curr];

  

    / * Используя индекс в обходе Inorder, создайте left и

    правый субтресс * /

    tNode->left = buildTree(in, pre, inStrt, inIndex - 1, mp);

    tNode->right = buildTree(in, pre, inIndex + 1, inEnd, mp);

  

    return tNode;

}

  
// Эта функция в основном создает unordered_map, затем
// вызывает buildTree ()

struct Node* buldTreeWrap(char in[], char pre[], int len)

{

    // Сохраняем индексы всех предметов, чтобы мы

    // мы можем быстро найти позже

    unordered_map<char, int> mp;

    for (int i = 0; i < len; i++)

        mp[in[i]] = i;

  

    return buildTree(in, pre, 0, len - 1, mp);

}

  
/ * Этот функционал здесь только для проверки buildTree () * /

void printInorder(struct Node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

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

    printInorder(node->right);

}

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

int main()

{

    char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' };

    char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' };

    int len = sizeof(in) / sizeof(in[0]);

  

    struct Node* root = buldTreeWrap(in, pre, len);

  

    / * Давайте проверим построенное дерево, напечатав

      Обход по инсордеру * /

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

    printInorder(root);

}

Выход:

Inorder traversal of the constructed tree is 
D B E A F C

Сложность времени: O (n)

Другой подход:
Используйте тот факт, что обход InOrder — левый-корневой-правый, а обход PreOrder — корневой-левый-правый. Кроме того, первый узел в обходе PreOrder всегда является корневым узлом, а первый узел в обходе InOrder является самым левым узлом в дереве.

Поддерживать две структуры данных: Stack (для хранения пути, который мы посетили при обходе массива PreOrder) и Set (для поддержки узла, в котором ожидается следующее правое поддерево).

1. Делайте ниже, пока не дойдете до самого левого узла.
Продолжайте создавать узлы из обхода PreOrder
Если самого верхнего элемента стека нет в наборе, свяжите созданный узел с левым потомком самого верхнего элемента стека (если есть), не выталкивая элемент.
В противном случае связать созданный узел с правым потомком самого верхнего элемента стека. Удалить верхний элемент стека из набора и стека.
Вставьте узел в стек.

2. Продолжайте извлекать узлы из стека до тех пор, пока либо стек не станет пустым, либо самый верхний элемент стека не сравнится с текущим элементом обхода InOrder. Когда цикл закончен, поместите последний узел обратно в стек и в набор.

3. Перейти к шагу 1.

Джава

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

import java.util.*;

  

public class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode(int x) { val = x; }

}

  

class BinaryTree {

    static Set<TreeNode> set = new HashSet<>();

    static Stack<TreeNode> stack = new Stack<>();

  

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

    public TreeNode buildTree(int[] preorder, int[] inorder)

    {

  

        TreeNode root = null;

        for (int pre = 0, in = 0; pre < preorder.length;) {

  

            TreeNode node = null;

            do {

                node = new TreeNode(preorder[pre]);

                if (root == null) {

                    root = node;

                }

                if (!stack.isEmpty()) {

                    if (set.contains(stack.peek())) {

                        set.remove(stack.peek());

                        stack.pop().right = node;

                    }

                    else {

                        stack.peek().left = node;

                    }

                }

                stack.push(node);

            } while (preorder[pre++] != inorder[in] && pre < preorder.length);

  

            node = null;

            while (!stack.isEmpty() && in < inorder.length && 

                    stack.peek().val == inorder[in]) {

                node = stack.pop();

                in++;

            }

  

            if (node != null) {

                set.add(node);

                stack.push(node);

            }

        }

  

        return root;

    }

  

    // Функция для печати дерева в Inorder

    void printInorder(TreeNode node)

    {

        if (node == null)

            return;

  

        / * первый рецидив на левом ребенке * /

        printInorder(node.left);

  

        / * затем распечатать данные узла * /

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

  

        / * теперь возвращаемся на правильного ребенка * /

        printInorder(node.right);

    }

  

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

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

  

        int in[] = new int[] { 9, 8, 4, 2, 10, 5, 10, 1, 6, 3, 13, 12, 7 };

        int pre[] = new int[] { 1, 2, 4, 8, 9, 5, 10, 10, 3, 6, 7, 12, 13 };

        int len = in.length;

  

        TreeNode root = tree.buildTree(pre, in);

  

        tree.printInorder(root);

    }

}

C #

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

using System;

using System.Collections.Generic;

  

public class TreeNode 

{

    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int x) { val = x; }

}

  

class GFG 

{

    static HashSet<TreeNode> set = new HashSet<TreeNode>();

    static Stack<TreeNode> stack = new Stack<TreeNode>();

  

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

    public TreeNode buildTree(int[] preorder, int[] inorder)

    {

        TreeNode root = null;

        for (int pre = 0, iN = 0; pre < preorder.Length;)

        {

            TreeNode node = null;

            do {

                node = new TreeNode(preorder[pre]);

                if (root == null)

                {

                    root = node;

                }

                if (stack.Count != 0) 

                {

                    if (set.Contains(stack.Peek())) 

                    {

                        set.Remove(stack.Peek());

                        stack.Pop().right = node;

                    }

                    else 

                    {

                        stack.Peek().left = node;

                    }

                }

                stack.Push(node);

            } while (preorder[pre++] != inorder[iN] && 

                     pre < preorder.Length);

  

            node = null;

            while (stack.Count != 0 && iN < inorder.Length && 

                   stack.Peek().val == inorder[iN]) 

            {

                node = stack.Pop();

                iN++;

            }

            if (node != null)

            {

                set.Add(node);

                stack.Push(node);

            }

        }

        return root;

    }

  

    // Функция для печати дерева в Inorder

    void printInorder(TreeNode node)

    {

        if (node == null)

            return;

  

        / * первый рецидив на левом ребенке * /

        printInorder(node.left);

  

        / * затем распечатать данные узла * /

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

  

        / * теперь возвращаемся на правильного ребенка * /

        printInorder(node.right);

    }

  

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

    public static void Main(String []args)

    {

        GFG tree = new GFG();

  

        int []iN = new int[] { 9, 8, 4, 2, 10, 5, 10, 

                                 1, 6, 3, 13, 12, 7 };

        int []pre = new int[] { 1, 2, 4, 8, 9, 5, 10, 

                                 10, 3, 6, 7, 12, 13 };

        int len = iN.Length;

  

        TreeNode root = tree.buildTree(pre, iN);

  

        tree.printInorder(root);

    }

}

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

Выход:

9 8 4 2 10 5 10 1 6 3 13 12 7

Спасибо Hardik Agarwal за предложенный подход.

Построить бинарное дерево по порядку и порядку

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

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

Построить дерево из заданных обходов Inorder и Preorder

0.00 (0%) 0 votes