预排序二进制搜索树插入

Question

一个痛苦而愚蠢的问题，我几乎羞于不敢问。在过去的4个小时里，我一直在寻找，测试了不同的算法，在纸上尝试了不少，但仍然无法正常工作。

我将为您提供项目实现的详细信息，但基本问题是：“如何处理在预排序二叉树中插入节点。

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

我只需要一个简单的算法。我尝试了这里给出的一个简单的插入算法(在stackoverflow上，但是好像不正确(也在纸上试过))；。

节点基本上是这样的：

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

插入数据只是唯一整数的列表。我用int作为键创建了一个节点，然后应该把这个节点添加到树中。我有根节点，它从一个空指针开始。

如果有什么不清楚，请原谅。

感谢您的帮助！

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

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

Answer 1

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

所以，一个可行的算法是:

1. 如果新节点小于根节点，请使其成为新根节点，并将现有树作为两个子节点之一指向。
2. 如果新节点大于根，但小于右子树的根，请以递归方式将其插入到左子树中。
3. 否则，请以递归方式将其插入到正确的子树中。

这不太可能产生一个非常平衡的树，但它应该有效。我可以想到至少一个其他简单的替代方案，毫无疑问，有一些方法可以使事情更加平衡，我将其留给读者作为练习;-）