Рекурсивно назначая позиции узлу в дереве двоичного поиска

Question

Здравствуйте, я ищу способ рекурсивно назначить позиции дерева индексу int, чтобы значение узла в позиции можно было поместить в массив.

Желаемые позиции дерева обозначаются в порядке уровня, где корневая позиция равна 1 (i), а левое дочернее устройство i находится в позиции 2i, а правый ребенок - 2i + 1 - как структура кучи. Нулевым детям не присваивается должность.

 1 
    /\ 
     2 3 
    /\ /\ 
    4 5 6 7 
     ... 

[1, 2, 3, 4, 5, 6, 7. ...] 

И наибольшая позиция в дереве должна быть размером с массив. Добавление нулей в качестве «пробела» желательно для моего вывода для проверки значений узла.

private int largestPos 
// first call: assignPositions(root, 1) 
assignPositions(node cur, int pos) { 
    parent = new node; 
    if curpos > largestPos 
     largestPos = curPos 

    if cur == null 
     parent.pos = pos 
    else 
    current.pos = pos 

    parent = cur 
    if cur.left != null 
     pos = 2 * pos 
     assignPositions(cur.left, pos) 
    if cur.right != null 
     pos = 2 * pos + 1 
     assignPositions(cur.right, pos) 
} 

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

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

Обновления для массива поиска в ширине:

public Key[] breadthFirstTraversal() { 

    @SuppressWarnings("unchecked") 
    Key[] keysFinal = new Key[largestPos]; 

    List<Key> queue = new List<Key>(); 
    List<Key> keysList = new List<Key>(); 
    List<Integer> positions = new List<Integer>(); 

    if (!isEmpty()) { 
     Node tempNode = root; 
     KeyValuePair<Key, Value> tempKey = null; 

     queue.add(tempNode); 

     while (!queue.isEmpty()) { 
      queue.reset(); 
      tempKey = queue.remove(); 
      keysList.add(tempKey); 

      tempNode = findKey(tempKey.getKey(), root); 

      // adds keys in order on level in list 
      if (tempNode.getLeftChild() != null) { 
       queue = addAtEnd(queue, tempNode.getLeftChild()); 
      } 
      if (tempNode.getRightChild() != null) { 
       queue = addAtEnd(queue, tempNode.getRightChild()); 
      } 
     } 

     for (int i = 1; i < largestPos + 1; i++) { 
      keysList.reset(); 
      tempKey = keysList.remove(); 
      tempNode = findKey(, root); 
      if (tempNode.getPosition() == i) { 
       keysFinal[i - 1] = tempKey; 
      } else { 
       keysFinal[i - 1] = null; 
      } 
     } 
    } 

    return keysFinal; 
} 

Answer 1

Вы пытаетесь pos работать на лев поддерева, но хочет, чтобы исходное значение для работы на праве поддерева. Поэтому не меняйте pos, просто введите выражение, которое вы хотите, в звонок assignPositions.

Затем вы продолжаете создавать новые узлы для каждого из них, которые вы посещаете, и я не вижу никакого массива, поэтому есть проблема, а не только проблема.