Достигнут обход по двоичному дереву только из обхода по порядку - PullRequest
Новая
       6

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

0 голосов
/ 03 марта 2019

У меня возник вопрос в моей задаче кодирования.

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

Ваша задача проста, учитывая post-order обход для полного двоичного дерева, вывести его in-order обход.

Элементы вдвоичное дерево имеет тип символа, т. е. каждый узел хранит одно символьное значение.

Формат ввода / вывода

Формат ввода:

Тольковвод одной строки, обозначающий обход по порядку.

Ограничения:

1 <= input.length <= 1000 </p>

Формат вывода:

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

Sample

Sample Input 0:

BCA

Пример вывода 0:

BAC

Ответы [ 2 ]

0 голосов
/ 03 марта 2019

У меня был готов полный ответ, но @EricWang обошел меня с реализацией.Итак, вот дополнительный ответ, описывающий процесс более подробно.Пожалуйста, примите его в качестве ответа.

Я собираюсь использовать обход после заказа DEBFGCA, так как полезно рассмотреть чуть больше узлов.

Поскольку деревоВ завершение, для любого данного узла мы знаем, что число дочерних элементов слева равно числу дочерних элементов справа.Следовательно, мы можем посмотреть на обход порядка 100 * и узнать, что он имеет структуру LLLRRRN, где L - обход левого поддерева в порядке, R - обход порядка в порядке.правое поддерево, а N - это сам узел.

В общем, мы знаем, что обход по левому поддереву после заказа - это символы от 0 до (tree.length - 1)/2 - 1, а обход по порядку:правильное поддерево - символы от (tree.length -1)/2 - 1 до tree.length - 2.Узел является последним символом, в tree.length - 1.

Очевидно, чтобы изменить это на обход в порядке, нам просто нужно идентифицировать левое и правое поддеревья, изменить их на обход в порядке изатем верните LLLNRRR.Мы можем использовать рекурсию для преобразования левого и правого поддеревьев в порядок.

Так, например, начните с DEBFGCA.Мы знаем, что структура LLLRRRN, поэтому левое поддерево DEB, правое поддерево FGC и узел A.Мы хотим превратить DEB в порядок ...

Процесс DEB.Мы знаем, что левое поддерево D, правое E, узел B.Оба поддерева имеют длину 1, так же как и листья.Дальнейшая рекурсия не требуется.Вернуть LNR, что составляет DBE.

Процесс FGC.Как и раньше, верните FCG.

Теперь мы знаем, что слева расположен порядок DBE, а справа - FCG.Возврат LLLNRRR, что составляет DBEAFCG.

0 голосов
/ 03 марта 2019

Вы можете сделать это динамически, с рекурсией.

Механизм

  • Разделить дерево на 3 части: left, right, root.
  • Повторно объедините их в следующем порядке: left, root, right.
  • Рекурсивно разделяйте, пока длина поддерева не станет единицей.

Код - в Java

PostToInOrder.java 

public class PostToInOrder {
    public static String convert(String post) {
        checkPerfect(post); // check whether tree is perfect,

        return convertInner(post);
    }

    private static String convertInner(String post) {
        int len = post.length();
        if (len == 1) return post; // base case,

        String left = post.substring(0, len >> 1); // left of post,
        String right = post.substring(len >> 1, len - 1); // right of post,
        char root = post.charAt(len - 1); // root of post,

        return convertInner(left) + root + convertInner(right);
    }

    private static void checkPerfect(String tree) {
        if (!isPerfect(tree)) throw new IllegalArgumentException("input is not perfect tree, size: " + tree.length());
    }

    private static boolean isPerfect(String tree) {
        int len = tree.length();
        if (len < 1) return false;

        while (len != 0) {
            if ((len & 1) == 0) return false;
            len >>= 1;
        }

        return true;
    }
}

PostToInOrderTest.java:
(Юнит-тест, через TestNG) 

import org.testng.Assert;
import org.testng.annotations.Test;

public class PostToInOrderTest {
    @Test
    public void test() {
        Assert.assertEquals(PostToInOrder.convert("BCA"), "BAC");
        Assert.assertEquals(PostToInOrder.convert("02146538A9CEDB7"), "0123456789ABCDE");

        Assert.assertEquals(PostToInOrder.convert("A"), "A"); // single element,
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void test_invalid_empty() {
        PostToInOrder.convert("");
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void test_invalid_notPerfect() {
        PostToInOrder.convert("AB");
    }
}

КСТАТИ:

  • Дерево, о котором идет речь, представляет собой perfect binary tree.
    Это подтип полного двоичного дерева.
    Полное дерево не обязательно идеально, его последний уровень может не содержать листьев.
    Например, AB - полное дерево, но не совершенное дерево..
...