Полная часть BST заняла немного времени, чтобы разобраться, что это на самом деле.Ваше требование также требует вставки уровня заказа.Я не могу сказать, что это «вставляет», но это создает BST на уровне порядка.
Входной список должен быть отсортирован первым.
Построение уровня заказа выполняется путем взятия корня и добавления его в BST, а затем разбиения того, что осталось налевый и правый списки, добавление их в список списков, затем обработка списка списков.Каждый раунд разделения и добавления в список списков является уровнем вставки.
Как было замечено, полная часть сложнее.Способ справиться с этим - вычислить корень для списка иначе, чем обычное сбалансированное дерево.В нормальном сбалансированном дереве корневой индекс имеет длину / 2.Чтобы BST был завершен, корневой индекс должен быть смещен, чтобы узлы, которые обычно появлялись бы с правой стороны корня, вместо этого появлялись с левой стороны корня.Пока вычисления работают для любого списка длин, каждый разделенный подсписок строится правильно.
Из того, что я могу сказать, вычисление смещения осуществляется путем увеличения смещения для каждого дополнительного элемента в длине до тех пор, пока вы не достигнете 1/2 ширины уровня.Итак, BST с высотой 4 имеет 8 элементов на самом низком уровне.Списки размером 8, 9, 10,… 15 создают BST с высотой 4. Для этих списков корневой индекс в списке равен 4, 5, 6, 7, 7, 7, 7, 7.
Кажется, работает.
public class Node<T extends Comparable<T>> {
protected Node<T> left;
protected Node<T> right;
protected T data;
}
public class BTree<T extends Comparable<T>> {
private Node<T> root = new Node<>();
public void addData(T data) {
Node<T> parent = root;
while (parent.data != null ) {
if ( data.compareTo( parent.data ) > 0 ) {
if ( parent.right == null )
parent.right = new Node<>();
parent = parent.right;
} else {
if ( parent.left == null )
parent.left = new Node<>();
parent = parent.left;
}
}
parent.data = data;
}
}
private void run() {
for ( int i = 2; i < 65; ++i ) {
List<Integer> intList = IntStream.range(1, i).boxed().collect(Collectors.toList());
BTree<Integer> bTree = new BTree<>();
List<List<Integer>> splitLists = new ArrayList<>();
splitLists.add(intList);
while (splitLists.size() > 0 ) {
List<List<Integer>> tSplitLists = new ArrayList<>();
for ( List<Integer> tIntList: splitLists) {
int length = tIntList.size();
// compute starting point
int mid = calcMid(length); // length/2 ; //+ calcOffset(length);
bTree.addData(tIntList.get(mid));
if ( mid - 0 > 0)
tSplitLists.add(tIntList.subList(0, mid));
if ( length - (mid+1) > 0)
tSplitLists.add(tIntList.subList(mid+1, length));
}
splitLists = tSplitLists;
}
bTree.printNode();
}
}
private int calcMid(int length) {
if ( length <= 4 )
return length / 2;
int levelSize = 1;
int total = 1;
while ( total < length ) {
levelSize *= 2;
total += levelSize;
}
int excess = length - (total - levelSize);
int minMid = (total - levelSize + 1) / 2;
if ( excess <= levelSize / 2 ) {
return minMid + (excess - 1);
} else {
int midExcess = levelSize/2;
return minMid + (midExcess - 1);
}
}
См. Как распечатать диаграмму двоичного дерева? код для печати двоичного дерева.
PS> Я уверен, что вы можетесделать его немного лучше, очистив и скопировав списки вместо того, чтобы каждый раз создавать новые.
РЕДАКТИРОВАТЬ: Вы пошли и получили код printNode, указанный выше?
1
2
/
1
2
/ \
1 3
3
/ \
/ \
2 4
/
1
И такна…