Создание бинарного дерева из строки - PullRequest
0 голосов
/ 02 июня 2019

Я пытаюсь построить дерево из строки. Строка имеет вид: ((. (.A.E)) (. I.O)), где 5 листовых узлов дерева представлены точкой.

Я не могу определить, как решить эту проблему; Я попытался настроить решение аналогичной проблемы, предлагаемой на этом сайте: https://www.geeksforgeeks.org/construct-binary-tree-string-bracket-representation/.

Буду очень признателен за любую помощь, которую вы можете оказать, когда я готовлюсь к написанию интервью.

Спасибо!

Ответы [ 2 ]

0 голосов
/ 02 июня 2019

Решение, которое я придумал, является итеративным решением, основанным на стеке. Есть несколько правил, которым нужно следовать:

  1. выталкивает все, что приходит в стек
  2. Если вы столкнулись с ) стека, начните удалять элементы, пока не встретите (, а затем выскакиваете это тоже.
  3. Когда вы добавляете элементы на шаге 2, сохраняйте их в векторе, кроме ) и (.
  4. Создайте узел дерева и отметьте дочерние элементы родителя как все элементы вектора.
  5. поместите родительский узел обратно в стек.

Давайте посмотрим на вашем примере: S = "((a($Z))(An))", для ясности изменено ' ' -> 'a'.

Примечание : стек растет вправо.

Stack["((a($Z"]
encounter ')'
Stack["((a"], vector<"Z$">
reverse vector -> vector<"$Z">
Parent Node -> N(id='1'), children -> <N(id='$'), N(id='Z')>
push N(1) to stack

Stack["((a1]
encounter ')'
Stack["("], vector<"1a">
reverse vector -> vector<"a1">
Parent Node -> N(id='2'), children -> <N(id='a'), N(id=1)>
push N(2) to stack

Stack["(2(An"]
encounter ')'
...

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

Код:

Node* solve(string s) {
    stack<Node *> st;
    int idx = 0, rt = 1;
    while (idx < s.size()) {
        Node *n = get_node(s[idx]);
        st.push(n);
        ++idx;

        if (st.top()->v == ')') {
            st.pop();
            vector<Node *> child;
            while (st.size() && st.top()->v != '(') {
                child.push_back(st.top()); st.pop();
            }
            if (st.top()->v == '(') st.pop();

            Node *par = get_node('0' + rt++);
            reverse(child.begin(), child.end());
            for (Node *t : child) {
                t->parent = par;
                par->child.push_back(t);
            }
            st.push(par);
        }
    }
    return st.top();
}

Полный рабочий код

Этот код является общей реализацией, поэтому любой узел может иметь столько же дочерних элементов, что и построение дерева n-arry. например:

input: ((a($Zk))(An))
output:
Parent: 4: 2 3
Parent: 2: a 1
Parent: 3: A n
Parent: 1: $ Z k
0 голосов
/ 02 июня 2019

Как я вижу, есть только некоторые правила, которым нужно следовать. В зависимости от обрабатываемого персонажа у вас есть следующие опции:

  1. Если это "(", это означает, что вы должны построить свое дерево глубже, влево или вправо, основываясь на действиях, которые вы предприняли до этого
  2. Если это «.», Вы должны прочитать следующий элемент в строке, чтобы определить значение узла, и после этого вы должны вернуться на один шаг в рекурсии как «.» представляет собой лист
  3. Если это ")", это означает, что вы завершили построение поддерева узла, и поэтому вы должны вернуться на один шаг в рекурсии снова

Несколько советов о том, как это реализовать:

  1. Напишите рекурсивную функцию, которая принимает строку в качестве ввода
  2. Функция также должна возвращать строку, представляющую строку, которая остается для дальнейшей обработки
  3. Если на каком-либо шаге ваша строка пуста, это означает, что строка, указанная для обработки, недействительна
  4. Вы должны проверять ")" каждый раз, когда заканчиваете строить левое или правое поддерево узла

Надеюсь, это поможет и удачи на ваших собеседованиях!

...