2015-08-14 5 views
0

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

 (a)    (1) 
    (x) (r) =>  (2) (3) 
    (o)(t)(t)(x)  (4)(5)(6)(7) 

Так что я могу затем использовать вызов таких как getIndex() на конкретный узел, чтобы вернуть его индекс.

Мой класс дерево:

public class BT<E>{ 
    E value; 
    BT<E> left, right; 
    int Index; 

    public BT(E value) 
    { 
     this.value=value; 
    } 

    public BT (E value, BT left, BT right) 
    { 
     this.value = value; 
     this.left = left; 
     this.right = right; 
    } 
+0

Вы можете пройтись по дереву еще раз после того, как полностью его создали, или пытаетесь инициализировать этот индекс во время первого прохода при создании дерева? – NoseKnowsAll

+0

Просто перемещайте свое дерево по слою. – talex

+0

@NoseKnowsAll Мне нужно, чтобы это было сделано после того, как дерево полностью создано. – RK2015

ответ

1

в ширину первого обхода.

Queue<BT> queue = new LinkedList<BT>() ; 

public void breadth(BT root) { 
    if (root == null) 
     return; 

    queue.clear(); 
    queue.add(root); 
    int index = 0; 
    while(!queue.isEmpty()){ 
     BT node = queue.remove(); 
     node.Index = index; 
     index++; 
     if(node.left != null) queue.add(node.left); 
     if(node.right != null) queue.add(node.right); 
    } 

} 

Адаптировано из here.

0

Итак, вы должны реализовать процедуру getIndex(int index), которая должна вернуть вам узел с этим индексом?

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

Эффективным решения для хранения полного бинарного дерева в массиве из-за O (1) доступа к нему обеспечивает. Храните узел n в индексе n в массиве и его дочерние узлы с индексом 2*n и (2*n) - 1. Но здесь ограничения заключаются в том, что дерево должно быть полным, а размер массива не является переменным (если бинарное дерево становится слишком большим, должен быть сделан больший массив (обычно в два раза больше), и все элементы должны быть скопированы).

Это удобное решение, так как:

  • узел доступа в O (1), но процедура, как addNode() стала бы амортизируется в O (1). (*)(*)
  • Узел не должен помнить, что это дочерние узлы ->this.left становится this.left() с реализацией left(), представленной ниже.

A возможная реализация для left() процедура.

static int[] binaryTreeArray = new int[maxTreeSize]; // BT of integers for example 
... 
public int left() { // returns integer or ... (type of your nodes) 
    return binaryTreeArray[(this.Index)*2]; // O(1) 
} 

(*)addNode() -как процедура добавления узлов в O (1) (binaryTreeArray[index] = nodeValue;) большую часть времени, но когда binaryTreeArray полон он должен будет сделать больший массив, который, как правило, в два раза как большой (O (n) для копирования). Можно показать, что это имеет амортизированную стоимость O (1), но для этого ответа это не добавило значения.

0

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

/* Method to set index based on level-order traversal of tree */ 
public void initIndices(BT root) { 
    int maxIndexSoFar = 0; 
    for (int d = 1; d <= root.height(); ++d) 
     maxIndexSoFar = setIndexAtLevel(root, d, maxIndexSoFar); 
} 

/* Method to set index of all nodes at a given level */ 
private int setIndexAtLevel(BT node, int level, int index) { 
    if (tree == null) 
     return index; 
    if (level == 1) { 
     index++; 
     node.setIndex(index); 
     return index; 
    } 
    else if (level > 1) { 
     int newIndex = setIndexAtLevel(node.left, level-1, index); 
     newIndex = setIndexAtLevel(node.right, level-1, newIndex); 
     return newIndex; 
    } 
    return -1; 
} 

Я оставлю вас, чтобы создать метод height() и setIndex() методы. Справедливое предупреждение, я не тестировал это вообще, поэтому прошу прощения за любые опечатки.

Смежные вопросы