Перестановка и сброс бинарного дерева поиска

Question

Я работал над двоичным деревом и хочу выяснить, есть ли какой-нибудь алгоритм для перетасовки дерева и сортировки по уровню?

Скажем, например, у меня есть массив следующим образом:

int[] values = new int[16] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
BinaryTree<int> tree = new BinaryTree<int>(values);

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

Answer 1

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

Ввод: значения

1. случайным образом выбирает значение в качестве корневого узла - скажем, r.
2. r-> left = рекурсивно построить случайное двоичное дерево из значений [0..r].
3. r-> right = рекурсивно построить случайное двоичное дерево из значений [r + 1..values.length () - 1].
4. возврат r.

Вы смотрите на перетасовку уже созданного бинарного дерева?

Answer 2

Вот алгоритм:

1. Создать массив из двоичного дерева.
2. Выберите элемент случайным образом из списка.
3. если root недоступен, выберите элемент в качестве корневого.
4. Выберите случайное значение от 0 до 1 одинаково. Если это 0 элемент идет в левое поддерево. Если это 1 элемент, идет в правильное поддерево.
5. если левое / правое поддерево отсутствует, свяжите узел с текущими узлами левого или правого потомка. В противном случае повторяйте шаг 4, пока не достигнете узла, где условие удовлетворяется.

Это будет иметь равномерное распределение.