二叉树的插入，而不排序

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

如果你改变

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结构的末端。

也可以看看：

• Lack of randomness in C rand()

---

如果你的树在每个节点追踪它的高度，你可以在你的null检查像添加后

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 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->left == NULL)
  root->left=insert(root->left,key);

你知道root->left为NULL，为什么做递归调用？

当然，同为未来其他

下面的代码只对最先三个节点。

如果两个左右都是非NULL不插入，那个时候有必要做两个分支的一个递归调用，你会考虑的关键（所以插入有序），以决定哪一个。注意2次测试为NULL你没有不正确的，如果您将有一个排序的树...

Answer 5

堆的建议是最完善的。你并不需要heapify什么，只是跟着，在指数k一个元件在2*k + 1和2*k + 2儿童的规则。

另一种方法，有用的时候有没有数组，但节点实时生成，是填补树级别明智的。请注意，在水平k有2 ** k槽，通过将k-bit整数方便索引。解读指数下跌树的路径（明确位告诉遵循左子，置位告诉遵循正确的），沿着线：

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