Преобразовать двоичное дерево -> BST (поддерживая исходную форму дерева)

Question

У меня есть двоичное дерево некоторой формы .Я хочу преобразовать его в дерево поиска BST той же формы .Является ли это возможным?

Я пробовал такие методы, как -

• Выполнить обход по порядку двоичного дерева и поместить содержимое в массив.Затем отобразите это в BST, учитывая условие (left val <= root <= right val).Это работает для некоторых случаев, но не для других. </li>

PS: я посмотрел на этот вопрос - Binary Trees.Проверка на похожую форму .Но легко сравнить 2 BST по схожести по форме.

Answer 1

Короткий ответ: вы не можете.BST требует, чтобы узлы следовали правилу left <= current <right.В приведенном вами примере: <a href="http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg" rel="noreferrer">http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg, если вы попытаетесь построить BST с тем же шаблоном, вы обнаружите, что это невозможно.

Однако, если вы хотите расширить определение BSTтак что это позволяет left <= current <= right (обратите внимание, что здесь current <= right разрешено, в отличие от более строгого определения) вы можете.Сортируйте все элементы и вставьте их в массив.Теперь выполните обход в порядке, заменяя значения в узлах каждым элементом в вашем массиве.Вот некоторый псевдокод: </p>

// t is your non-BST tree, a is an array containing the sorted elements of t, i is the current index into a
index i = 0
create_bst(Tree t, Array a)
{
  if(t is NIL)
    return;
  create_bst(t->left, a)
  t->data = a[i]
  i++
  create_bst(t->right, a)
}

Однако результат не будет истинным BST.Если вам нужен настоящий BST, максимально приближенный к исходной форме, вы снова помещаете элементы в отсортированный массив, но на этот раз вставляете их в BST.Порядок, в котором вы их вставляете, определяется размерами поддеревьев исходного дерева.Вот некоторый псевдокод:

// left is initially set to 0
create_true_bst(Tree t, BST bt, array a, index left)
{
  index i = left + left_subtree(t)->size
  bt->insert(a[i])
  if(left_subtree(t)->size != 0)
  {
    create_true_bst(t->left, bt, a, left)
    create_true_bst(t->right, bt, a, i + 1)
  }
}

Однако это не гарантирует, что форма будет такой же.

Answer 2

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

Answer 3

Я бы просто сделал два обхода в порядке.При первом обходе получите значения из дерева и поместите их в кучу.Во втором получите значения в порядке из кучи и поместите их в дерево.Это выполняется за O (n · log n) времени и O (n) пробела.

Answer 4

Метод, который вы описываете, гарантированно сработает, если вы правильно его реализуетеПорядок обхода в двоичном дереве уникален и определяет порядок элементов.Если вы сортируете элементы по значению, а затем вставляете их в соответствии с этим порядком, то всегда будет верно, что

left subtree <= root <= right subtree

для каждого узла, учитывая, что это порядок, в котором вы проходите их, иучитывая, что вы отсортировали их в этом порядке.