Вставка в двоичное дерево (без порядка)

Question

Как бы вы реализовали дерево, не упорядочив его?

Answer 1

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

Layer0 - root -> 2^0 = 1 (first element) 
Layer1 --------> 2^1 = 2 (next two elements) 
Layer2 --------> 2^2 = 4 (next four elements)

Относительно тривиально разрушить структуру в следующей форме: [4], [5 | 2], [7 | 3 | 6 | 8]

То, что вы, вероятно, хотите, это иметь отношения, в которых 4 имеет детей 5 и 2, дети 5 лет - 7, а дети 3 и 2 - дети6 и 8.

Таким образом, вопрос заключается в том, как во время итерации по этому массиву узнать, каковы дети данного числа?Предполагая, что вы расположили элементы последовательно в индексируемой структуре данных, такой как массив, и каждый элемент имеет ровно два дочерних элемента или ни одного, вы можете создать свой «обход дерева» следующим образом:

Children of 4, которыйкак в индексе 0 (корень), будут индексы 2 ^ 0 и 2 ^ 1 (индексы 1 и 2). Дочерние элементы для индексов 1 и 2 будут (2 ^ 1 + 1) и (2 ^ 1 + 2).Дочерние элементы для индекса 2 будут 2 ^ 2 + 1 и 2 ^ 2 + 2.

Таким образом, схема сводится к 2 ^ i + 1 (для левого потомка), 2 ^ i + 2 (дляправильный ребенок).Я надеюсь, что это поможет с вашей реализацией дерева.

Answer 2

Самый простой способ сделать это.Хотя это не должно происходить в реальной жизни.8)

Queue queue = new Queue();

function add(input){
  element = input.popFirst();
  if(element == null) return false;

  node = queue.get();
  node.value = element;
  node.left = new Node();
  queue.put(node.left);
  node.right = new Node();
  queue.put(node.right);
  return true;
}

Node root = new Node();
queue.put(root);
while(add(input)){}
while(!queue.isEmpty){
  destroy queue.get();
}

Answer 3

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

first_node_of_a_level = (branches^level)-1

Затем выберите дочерний узел того уровня, который вы хотите.Например, корневой узел имеет значение (2 ^ 0) -1, что является индексом 0.

The first node on level 1 is (2^1)-1 = 1.
The first node on level 2 is (2^2)-1 = 3.
The first node on level 3 is (2^3)-1 = 7.

Это очень распространенная реализация, используемая в двоичных кучах .Статья в Википедии дает вам основы поиска «потомка» или «родителя» по заданному индексу узла в массиве.

Answer 4

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

Если предположить, что ваши входные данные хранятся в inputArray[] input;, каков индекс первого узла, который не является листом???

input.length / 2 - 1  =>  7 / 2 - 1  =>  2  =>  input[2] is 2

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

leftChild = parentIndex * 2 + 1;
rightChild = parentIndex * 2 + 2;
EG: Children of node at index 2 (value 2): left=5 (value 6), right=6(value 8)
NOTE: Watch for ArrayIndexOutOfBound that means that children are missing

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

Answer 5

У вас также может быть объект, упорядоченный по индексу, который вы положили в обычное двоичное дерево

class indexedObject implements Comparable{
    public Int index;
    public int data;

    @Override
    public int compareTo(Object t) {
        if (t instanceof indexedObject) {
            return index.compareTo(((indexedObject)t).index);
        }
    }      
}

затем его можно вставить в двоичное дерево

Answer 6

Я просто могу придумать, как создать дерево, подобное приведенному

.

size( n ) = size of the subtree rooted in n
left( n ) = left child of n
right( n ) = right child of n

затем следует вставка (x вставляемый узел, n корень текущего дерева [sub])

insert( x, n ) {

 if ( left(n) == null ) {
    left(n) = x;
    return;
 } else if ( right(n) == null ) {
    right(n) = x;
    return;
 } else {
    if ( size( left(n) ) <= size( right(n) ) {
       insert( x, left(n) );
    } else {
       insert( x, right(n) );
    }
 }

в основном каждый пытается вставить новое значение на стороне дерева, которое сейчас является меньшим. если оба имеют одинаковый размер, слева предпочтительнее, чем справа.

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