Построение бинарного дерева из его обходов - PullRequest
Новая
       4

Построение бинарного дерева из его обходов

1 голос
/ 15 ноября 2011

Я пытаюсь построить двоичное дерево (несбалансированное), учитывая его обходы. В настоящее время я делаю предварительный заказ + заказ, но когда я выясню это, заказ уже не будет проблемой.

Я понимаю, что по этой теме уже есть некоторые вопросы, но никто из них, похоже, не ответил на мой вопрос. У меня есть рекурсивный метод, который использует Preorder и Inorder двоичного дерева для его реконструкции, но по какой-то причине не может связать корневой узел с последующими дочерними элементами.

Примечание: я не хочу решения. Я пытался понять это в течение нескольких часов и даже записал рекурсию на бумаге, и все, кажется, хорошо ... поэтому я, должно быть, упускаю что-то тонкое. Вот код: 

    public static <T> BinaryNode<T> prePlusIn( T[] pre, T[] in)
{
    if(pre.length != in.length)
        throw new IllegalArgumentException();

    BinaryNode<T> base = new BinaryNode();
    base.element = pre[0]; // * Get root from the preorder traversal.
    int indexOfRoot = -1 ;

    if(pre.length == 0 && in.length == 0)
        return null;

    if(pre.length == 1 && in.length == 1 && pre[0].equals(in[0]))
        return base; // * If both arrays are of size 1, element is a leaf.

    for(int i = 0; i < in.length -1; i++){
        if(in[i].equals(pre[0])){    // * Get the index of the root
            indexOfRoot = i; // in the inorder traversal.
            break;
        } 

    }   // * If we cannot, the tree cannot be constructed as the traversals differ.

        if (indexOfRoot == -1) throw new IllegalArgumentException();

    // * Now, we recursively set the left and right subtrees of 
    // the above "base" root node to whatever the new preorder
    // and inorder traversals end up constructing.

    T[] preleft = Arrays.copyOfRange(pre, 1, indexOfRoot + 1);
    T[] preright = Arrays.copyOfRange(pre, indexOfRoot + 1, pre.length);
    T[] inleft = Arrays.copyOfRange(in, 0, indexOfRoot);
    T[] inright = Arrays.copyOfRange(in, indexOfRoot + 1, in.length);

    base.left = prePlusIn( preleft, inleft); // * Construct left subtree.
    base.right = prePlusIn( preright, inright); // * Construc right subtree.

    return base; // * Return fully constructed tree
}

По сути, я создаю дополнительные массивы, которые содержат обходы левого и правого поддерева до и по порядку (это кажется ужасно неэффективным, но я не мог придумать лучшего способа без вспомогательных методов).

Любые идеи будут весьма признательны.

Примечание: при отладке кажется, что корневая заметка никогда не получает соединения с дополнительными узлами (они остаются нулевыми). Из того, что я вижу, этого не должно быть ...

РЕДАКТИРОВАТЬ: Чтобы уточнить, метод выбрасывает IllegalArgumentException @ line 21 (else ветвь цикла for, который должен * только *1017* быть брошен, если обходы содержат различные элементы.

EDIT2 : понял это благодаря полезному сообщению от @Philip (по совпадению, у нас то же имя ... забавно!). Однако, если у кого-нибудь есть какие-либо советы по повышению эффективности, я был бы признателен за вводную информацию.

1 Ответ

2 голосов
/ 15 ноября 2011

этот код мне очень подозрителен 

for(int i = 0; i < in.length -1; i++){
    if(in[i].equals(base.element)){    // * Get the index of the root
        indexOfRoot = i; // in the inorder traversal.
        break;
    } // * If we cannot, the tree cannot be constructed as the traversals differ.
    else throw new IllegalArgumentException();
}

Вы вводите цикл, и i устанавливается в 0, если i меньше in.length - 1, вы вычисляете тело цикла, которое является выражением if. В этот момент произойдет одна из двух вещей

  1. in[i] равно base.element, в этом случае indexOfRoot будет установлено в 0, и вы выйдете из цикла
  2. Вы бросаете исключение

В любом случае вы на самом деле никогда не увеличиваете i

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

int indexOfRoot = -1; //an impossible value
for(int i = 0; i < in.length -1; i++){
    if(in[i].equals(base.element)){    // * Get the index of the root
        indexOfRoot = i; // in the inorder traversal.
        break;
    } 
} 
if(indexOfRoot == -1){//if the root was never set
    throw new IllegalArgumentException();
}

хотя это все-таки некрасиво (с одной стороны, base.element никогда не меняется, поэтому вы можете использовать pre[0] для ясности). И ни в коем случае я не уверен, что это полностью правильно. Тем не менее, это, вероятно, ближе к тому, что вы хотите

...