首页 文章

预订二进制搜索树插入

提问于
浏览 次
2

一个痛苦的愚蠢问题，我几乎要羞于问 . 我一直在寻找过去的4个小时，测试了不同的算法，在纸上尝试了不少，仍然无法让它工作 .

我将免除项目实现的细节，但基本问题是：“如何处理在预订二进制树中插入节点 .

通过预订BST，我的意思是所有节点都应该以这样的方式插入，使用预订遍历（例如打印）遍历树应该按升序打印节点 .

我只需要一个简单的算法 . 我尝试了一个简单的插入算法（在stackoverflow上，但它似乎是不正确的（也在纸上尝试过））;.

节点基本上是这样的：

typedef struct testNode{
    int key;
    struct testNode *leftChild;
    struct testNode *rightChild;
}NODE;

插入数据只是一个唯一整数的列表 . 我创建一个以int作为键的节点，然后将该节点添加到树中 . 我有根节点，它以NULL指针开始 .

对不起，如果有什么不清楚 .

谢谢您的帮助！

编辑：基于下面提供的算法，这是我想出的：

void insert(NODE **tree,int key){
if(*tree){
    if ((*tree)->key >= key){
        //Insert before this .....
        NODE *temp = createNode(key);
        temp->lc = (*tree);
        (*tree) = temp;

    }
    else if(!(*tree)->rc){
        //Right Child doesn't exist ....
        insert(&(*tree)->lc,key);
    }
    else if((*tree)->rc->key < key){
        //Right child exists and is smaller than spread ... insert left ...
        insert(&(*tree)->lc,key);
    }
    else{
        //Right child exists and is greater than spread ... insert right ...
        insert(&(*tree)->rc,key);
    }
    //If the code as progressed to this point, insertion must have occured, 
            //and the code returns ......   
} else {
    //the **tree pointer points to NULL. Insert here ....
    SPREADNODE *temp = createSpreadNode(spread);
    //temp->lc = (*tree);
    (*tree) = temp;
}
}
c binary-search-tree insertion preorder

1 回答

  • 2

    考虑预先订购的BST的定义：根节点是最小的元素，它的两个子节点或预先排序的树，使得右子树的根大于左子树中的任何值 .

    因此，一种可行的算法是：

    • 如果新节点小于根节点，则将其设置为新根节点，并将现有树指向两个子节点之一 .

    • 如果新节点大于根，但小于右子树的根，则以递归方式将其插入左子树 .

    • 否则，递归地将其插入到右子树中 .

    这不太可能产生一个非常 balancer 的树，但它应该工作 . 我至少可以想到一个简单的替代方案，毫无疑问，我将这些东西作为练习留给读者的方式更加 balancer ;-)

    回复于

相关问题