добавление узла в полное дерево

Question

пытается создать полное дерево с нуля в C ++

1st node = root
2nd node = root->left
3rd node = root->right
4th node = root->left->left
5th node = root->left->right
6th node = root->right->left
7th node = root->right->right

, где дерево будет выглядеть примерно так:

                 NODE
              /        \
          NODE          NODE
       /        \    /        \
    NODE      NODE  NODE      NODE
    /
NEXT NODE HERE

как мне узнать, где будет следующий узелпойти, чтобы я мог просто использовать одну функцию для добавления новых узлов?например, восьмой узел будет размещен в корне-> слева-> слева-> слева

, цель состоит в том, чтобы вписать 100 узлов в дерево с помощью простого цикла for с "insert (Node * newnode)" вэто вместо того, чтобы делать по одному за раз.это превратилось бы во что-то уродливое как:

100th node = root->right->left->left->right->left->left

Answer 1

Предполагая, что дерево всегда завершено, мы можем использовать следующую рекурсию.Это не дает наилучшего результата, но его легко понять

Node* root;
Node*& getPtr(int index){
    if(index==0){
       return root;    
    }
    if(index%2==1){
       return (getPtr( (index-1)/2))->left;
    }
    else{
       return (getPtr( (index-2)/2))->right;
    }
}

, а затем использовать его как

for(int i = 0; i<100; ++i){
  getPtr(i) = new Node( generatevalue(i) );
}

Answer 2

 private Node addRecursive(*Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    if (value < current.value) {
        current->left = addRecursive(current->left, value);
    } else if (value > current->value) {
        current->right = addRecursive(current->right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
 }

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

Answer 3

Предположим, что root - это узел № 1, потомки root - это узел № 2 и узел № 3 и т. Д.Затем можно найти путь к узлу # k с помощью следующего алгоритма:

1. Представляет k в виде двоичного значения, k = { k_{n-1}, ..., k_0 }, где каждый k_i равен 1 биту, i = {n-1} ... 0.
2. Для перехода от корня к узлу # k требуется n-1 шагов, определяемых значениями k_{n-2}, ..., k_0, где
   1. , если k_i = 0, то идти налево
   2. если k_i = 1, тогда идите направо

Например, чтобы вставить узел № 11 (двоичный файл 1011) в полное дерево, вы должны вставитьэто как root-> left-> right-> right (как указано в 011 двоичного файла 1011).

Используя алгоритм, приведенный выше, было бы просто написать функцию, которая при любомk, вставьте узел # k в полное дерево в нужное место.Узлы даже не нужно вставлять по порядку, пока обнаруживаются новые узлы, созданные должным образом (т.е. как правильные левые или правые дочерние элементы, соответственно).

Answer 4

Используйте структуру данных queue для завершения построения полного двоичного дерева.STL предоставляет std::queue.

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

// Pass double pointer for root, to preserve changes
void insert(struct node **root, int data, std::queue<node*>& q)
{
    // New 'data' node
    struct node *tmp = createNode(data);

    // Empty tree, initialize it with 'tmp'
    if (!*root)
        *root = tmp;
    else
    {
        // Get the front node of the queue.
        struct node* front = q.front();

        // If the left child of this front node doesn’t exist, set the
        // left child as the new node.
        if (!front->left)
            front->left = tmp;

        // If the right child of this front node doesn’t exist, set the
        // right child as the new node.
        else if (!front->right)
            front->right = tmp;

        // If the front node has both the left child and right child, pop it.
        if (front && front->left && front->right)
            q.pop();
    }

    // Enqueue() the new node for later insertions
    q.push(tmp);
}