Рубрики

Построить двоичное дерево из строки с представлением в скобках

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

Примеры:

Input : "1(2)(3)" 
Output : 1 2 3
Explanation :
           1
          / \
         2   3
Explanation: first pair of parenthesis contains 
left subtree and second one contains the right 
subtree. Preorder of above tree is "1 2 3".  

Input : "4(2(3)(1))(6(5))"
Output : 4 2 3 1 6 5
Explanation :
           4
         /   \
        2     6
       / \   / 
      3   1 5   

Мы знаем, что первый символ в строке — корень. Подстрока в первой соседней паре скобок предназначена для левого поддерева, а подстрока во второй паре скобок — для правого поддерева, как показано на диаграмме ниже.

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

C ++

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

   данная строка * /

#include <bits/stdc++.h>

using namespace std;

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

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

struct Node {

    int data;

    Node *left, *right;

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

Node* newNode(int data)

{

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

    node->data = data;

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

    return (node);

}

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

void preOrder(Node* node)

{

    if (node == NULL)

        return;

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

    preOrder(node->left);

    preOrder(node->right);

}

  
// функция, возвращающая индекс закрывающей скобки

int findIndex(string str, int si, int ei)

{

    if (si > ei)

        return -1;

  

    // Встроенный стек

    stack<char> s;

  

    for (int i = si; i <= ei; i++) {

  

        // если открывающая скобка, нажмите ее

        if (str[i] == '(')

            s.push(str[i]);

  

        // если закрывающая скобка

        else if (str[i] == ')') {

            if (s.top() == '(') {

                s.pop();

  

                // если стек пуст, это

                // требуемый индекс

                if (s.empty())

                    return i;

            }

        }

    }

    // если не найдено, возвращаем -1

    return -1;

}

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

Node* treeFromString(string str, int si, int ei)

{

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

    if (si > ei)

        return NULL;

  

    // новый корень

    Node* root = newNode(str[si] - '0');

    int index = -1;

  

    // если следующий символ равен '(' найти индекс

    // его дополнение ')'

    if (si + 1 <= ei && str[si + 1] == '(')

        index = findIndex(str, si + 1, ei);

  

    // если индекс найден

    if (index != -1) {

  

        // вызов левого поддерева

        root->left = treeFromString(str, si + 2, index - 1);

  

        // вызов правильного поддерева

        root->right = treeFromString(str, index + 2, ei - 1);

    }

    return root;

}

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

int main()

{

    string str = "4(2(3)(1))(6(5))";

    Node* root = treeFromString(str, 0, str.length() - 1);

    preOrder(root);

}

python3

# Python3 программа для создания
# двоичное дерево из заданной строки

  
# Вспомогательный класс, который выделяет новый узел

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = self.right = None

  
# Этот функционал здесь только для проверки

def preOrder(node):

    if (node == None): 

        return

    print(node.data, end = " "

    preOrder(node.left) 

    preOrder(node.right)

  
# функция для возврата индекса
# закрыть скобки

def findIndex(Str, si, ei):

    if (si > ei): 

        return -1

  

    # Встроенный стек

    s = []

    for i in range(si, ei + 1):

  

        # если открыта скобка, нажмите на нее

        if (Str[i] == '('): 

            s.append(Str[i]) 

  

        # если закрыть круглые скобки

        elif (Str[i] == ')'): 

            if (s[-1] == '('):

                s.pop(-1

  

                # если стек пуст, это

                # требуемый индекс

                if len(s) == 0

                    return i

    # если не найден return -1

    return -1

  
# функция для построения дерева из String

def treeFromString(Str, si, ei):

      

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

    if (si > ei): 

        return None

  

    # новый корень

    root = newNode(ord(Str[si]) - ord('0'))

    index = -1

  

    # если следующий символ '' '

    # индекс его дополнения ')'

    if (si + 1 <= ei and Str[si + 1] == '('): 

        index = findIndex(Str, si + 1, ei) 

  

    # если индекс найден

    if (index != -1):

  

        # вызов левого поддерева

        root.left = treeFromString(Str, si + 2

                                     index - 1

  

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

        root.right = treeFromString(Str, index + 2

                                            ei - 1)

    return root

  
Код водителя

if __name__ == '__main__':

    Str = "4(2(3)(1))(6(5))"

    root = treeFromString(Str, 0, len(Str) - 1

    preOrder(root)

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


Выход:

4 2 3 1 6 5 

Эта статья предоставлена Чхави . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Построить двоичное дерево из строки с представлением в скобках

0.00 (0%) 0 votes