Рубрики

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

Деревья, Стек

Дана строка str, которая содержит троичное выражение, которое может быть вложенным. Задача — преобразовать данное троичное выражение в двоичное дерево и вернуть корень.

Примеры:

Input: str = "a?b:c"
Output: a b c
  a
 / \
b   c
The preorder traversal of the above tree is a b c.

Input: str = "a?b?c:d:e"
Output: a b c d e
    a
   / \
  b   e
 / \
c   d

Подход: это стековый подход к данной проблеме. Поскольку троичный оператор имеет ассоциативность справа налево, строка может быть пройдена справа налево. Возьмите буквы одну за другой, пропуская буквы ? и ':', поскольку эти буквы используются для определения того, будет ли текущая буква (алфавит [от a до z]) помещаться в стек или использоваться для извлечения двух верхних элементов из вершины стека, чтобы сделать их дочерними элементами текущая буква, которая затем сама помещается в стек. Это формирует дерево снизу вверх, и последний оставшийся элемент в стеке после обработки всей строки является корнем дерева.

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Структура узла

struct Node {

    char data;

    Node *left, *right;

};

  
// Функция для создания нового узла

Node* createNewNode(int data)

{

    Node* node = new Node;

    node->data = data;

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

    return node;

}

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

void preorder(Node* root)

{

    if (root == NULL)

        return;

    cout << root->data << " ";

    preorder(root->left);

    preorder(root->right);

}

  
// Функция для преобразования выражения в двоичное дерево

Node* convertExpression(string str, int i)

{

    stack<Node*> s;

  

    // Если буква последняя

    // строка или имеет тип: letter: или? letter:

    // толкаем указатель узла, содержащий

    // письмо в стек

    for (i = str.length() - 1; i >= 0;) {

        if ((i == str.length() - 1)

            || (i != 0 && ((str[i - 1] == ':'

                            && str[i + 1] == ':')

                           || (str[i - 1] == '?'

                               && str[i + 1] == ':')))) {

            s.push(createNewNode(str[i]));

        }

  

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

        // это означает, что верхние 2 узла в стеке в настоящее время являются

        // левый и правый потомок текущего узла

        // Так что вставьте эти элементы и назначьте их как

        // потомки текущего буквенного узла, а затем

        // вставляем этот узел в стек

        else {

            Node* lnode = s.top();

            s.pop();

            Node* rnode = s.top();

            s.pop();

            Node* node = createNewNode(str[i]);

            node->left = lnode;

            node->right = rnode;

            s.push(node);

        }

        i -= 2;

    }

  

    // Наконец, будет только 1 элемент

    // в стеке, который будет

    // корень двоичного дерева

    return s.top();

}

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

int main()

{

    string str = "a?b?c:d:e";

  

    // Преобразовать выражение

    Node* root = convertExpression(str, 0);

  

    // Распечатать обход предзаказа

    preorder(root);

  

    return 0;

}

Выход:

a b c d e

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

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

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

0.00 (0%) 0 votes