Создание BST из массива - PullRequest
Новая
       30

Создание BST из массива

1 голос
/ 24 марта 2011

Мне нужно создать двоичное дерево поиска следующим (странным) образом:

Мне дан массив (A [n]).[1] становится корнем дерева.

  • Затем я вставляю A [1] + A [2] в левое поддерево (subtree1, используется ниже) корня, а также вставляю A [1] -A [2]к правому поддереву (поддереву2) корня.

  • Я вставляю A [1] + A [2] + A [3] в левое поддерево поддерева 1 (поддерево3) и A[1] + A [2] -A [3] к правому поддереву поддерева 1 (subtree4).

  • Затем я вставляю A [1] -A [2] + A[3] к левому поддереву поддерева 2 (поддерево5) и A [1] -A [2] -A [3] к правому поддереву поддерева 2 (поддерево6).

  • Iповторите для subtree3, subtree4, subtree5, subtree6, пока я не достигну конца массива.

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

Я понимаю, что янужно использовать концепцию рекурсии, но в модификациив порядке.Напечатав мою проблему здесь и попытавшись объяснить ее кому-то другому, помимо моего мозга, я действительно сформировал ее таким образом, который дал мне некоторые идеи, чтобы попытаться, но я вижу проблему, с которой сталкиваюсь, как обычную проблему, так что, возможно, вы могли бы датьмне несколько советов о том, как использовать рекурсию для построения дерева.

Оглядываясь на другие вопросы и дискуссии, я понимаю, что существует политика, запрещающая целые решения, поэтому я хотел прояснить, что яне прося решение, но для руководства к нему.Если кто-то захочет посмотреть, я могу показать вам, что я уже сделал.

1 Ответ

0 голосов
/ 24 марта 2011

Способ сделать рекурсию - всегда предполагать, что у вас уже есть рабочая функция. Итак, давайте посмотрим [с использованием синтаксиса Java] ... 

Tree buildTree(int currentSum, int[] array, int index, boolean sign);

Предположим, это работает. Тогда вам нужно сделать, чтобы построить дерево с индексом я? 

// current value to look at at this level
int curValue = array[index];
// depending on sign, it may be negative
if (!sign) { 
  curValue *= -1;
}
// add it to the running total
int nodeValue = currentSum + curValue;
Node nd = new Node(nodeValue);

nd.left = buildTree(nodeValue, array, index + 1, true);
nd.right = buildTree(nodeValue, array, index + 1, false);

Вот и все. Вам нужно позаботиться о крайних случаях: index = array.length, создание самого первого узла и т.

...