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

Question

Как реализовать дерево без его заказа?

Answer 1

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

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. 

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

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

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

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

тогда следует для вставки (х узел должен быть вставлен, п корень из ток [суб] дерево)

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)); 
    } 
} 

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

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

Answer 4

Так что, если вы соберетесь разбивая свое дерево следующим образом: Каждый слой представляет собой мощность 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.

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

Дети 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 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

Если вы хотите освоить эту вы можете взглянуть на 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 (что-то с целочисленным значением и ссылкой узла), а затем добавить к каждому узлу без листьев своих детей. Вероятно, вы можете подумать над лучшими алгоритмами, которые требуют меньше дополнительной памяти или используют рекурсию в качестве дополнительной домашней работы!