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

Question

Есть ли способ вставить новый узел в двоичное дерево (не bst) без сравнения значений ключей?Следующий код работает только для самых первых трех узлов.

node *insert (node *root, int *key) {

if (root==NULL) {
    root=newNode(root, key);
    return root;
}

else if (root->left == NULL)
    root->left=insert(root->left,key);
else if  (root-> right == NULL)
    root->right=insert(root->right,key);

return root;

}

Answer 1

Совет кучи является наиболее обоснованным.Вам не нужно ничего складывать в кучу, просто следуйте правилам, что у элемента с индексом k есть дочерние элементы на 2*k + 1 и 2*k + 2.

Другой подход, полезный, когда нет массива, кромеузлы генерируются на лету, то есть заполнять дерево по уровням.Обратите внимание, что на уровне k есть 2 ** k слотов, удобно индексируемых k-битным целым числом.Интерпретировать индекс как путь вниз по дереву (чистый бит говорит следовать за левым потомком, установленный бит говорит следовать за правым) вдоль строк:

        void insert_node(struct node * root, struct node * node, unsigned mask, unsigned path)
        {
            while ((mask >> 1) != 1) {
                root = mask & path? root->right: root->left;
            }
            if (mask & path) {
                assert (root->right == NULL);
                root->right = node;
            } else {
                assert (root->left == NULL);
                root->left = node;
            }
        }

        void fill_level_k(struct node * root, unsigned k)
        {
            unsigned slots = 1 << k;
            for (unsigned slot = 0; slot < slots; slot++) {
                struct node * node = generate_new_node();
                insert_node(root, node, slots, slot);
            }
        }

Answer 2

Вы можете просто отслеживать высоту каждого узла и всегда вставлять его в сторону с меньшим количеством дочерних элементов:

node *insert (node *root, int *key) {
    if (root==NULL) {
        root=newNode(root, key);
        root->height = 0
    }
    else if (root->left == NULL) {
        insert(root->left,key);
    }
    else if (root->right == NULL) {
        insert(root->right,key);
    }
    else if (root->left->height <= root->right->height) {
        insert(root->left,key);
    } else {
        insert(root->right,key);
    }
    root->height++
}

Answer 3

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

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

void insertNode(node *&root, node *newNode) {
    if (root == NULL) { 
         root = newNode;
         return;
    }
    if (root->left == NULL) {
        root-left = newNode;
        return;
    }
    helperInsert(root->left, newNode);
    return;
}

Этоустановит голову (при условии, что я правильно понял подпись), а в противном случае проверим левого ребенка.

void helperInsert(node *it, node *newNode) {
    if (it->left == NULL) {
        it->left = newNode;
        return;
    }
    helperInsert(it->left, newNode);
    return;
}

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

Answer 4

Если вы измените

else if  (root-> right == NULL)

на

else

, то это будет иметь эффект постоянного добавления справа.

---

Если вы хотите, чтобы он выбирал случайным образом, добавьте вызов к srand вне этой функции.

srand(time(NULL));

Затем в этой функции вызовите

else if (rand() > MAX_RAND / 2) {
    root->right = insert(root->right, key);
} else {
    root->left = insert(root->left, key);
}

в конце существующей структуры if / else.

См. Также:

• Отсутствие случайности в C rand ()

---

Если ваше дерево отслеживает свою высоту в каждом узле, вы можете добавить его после проверки на нольчто-то вроде

else if (root->left->height <= root->right->height) {
    root->left = insert(root->left, key);
} else {
    root->right = insert(root->right, key);
}

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

root->height = 1 + ((root->left->height > root->right->height) ? root->left->height : root->right->height);

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

---

Люди, предлагающие использовать кучу, предлагают использовать индексы в качестве порядка.Это бесполезно как куча, но это создаст сбалансированное двоичное дерево.Таким образом, корневой узел будет первым вставленным, а самый последний - самым правым.

Answer 5

В

else if (root->left == NULL)
  root->left=insert(root->left,key);

вы знаете, root->left НЕДЕЙСТВИТЕЛЕН, так зачем делать рекурсивный вызов?

Конечно, то же самое для следующего иначе

Следующий код работает только для первых трех узлов.

Если оба left и right не равны NULL, вы невставьте, чтобы в этот раз необходимо было выполнить рекурсивный вызов в одной из двух ветвей, и вы рассмотрите ключ (так что вставьте упорядоченный), чтобы решить, какой из них.Обратите внимание, что 2 теста на NULL, которые вы сделали, не верны, если вы вставляете для сортировки дерева ...