二叉搜索树的先序插入

Question

一个非常愚蠢的问题，我都快不好意思问了。我已经搜索了过去4个小时，测试了不同的算法，尝试了很多，但仍然无法使其工作。

我将跳过项目实现的详细信息，但基本问题是：“如何处理在先序二叉树中插入节点。”

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

我只需要一个简单的算法。我尝试了在stackoverflow上提供的一个简单的插入算法（也在纸上尝试过），但似乎不正确；

节点基本上像：

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

插入数据只是一列唯一的整数。我创建一个以该整数作为键的节点，然后应将该节点添加到树中。我有根节点，它最初为空指针。

如果有不清楚的地方请谅解。

感谢您的帮助！

编辑：基于下面提供的算法，我得出了以下结果：

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

- GCon

---

希望你只是错误地复制了那个结构体。 - paddy

当你说“预订”二叉树时，是指已经排序的BST还是与先序遍历有关？ - Yaniv

是的，这个结构体是匆忙编写的，我会编辑它。Pre-Ordered 指的是我应该将节点插入树中，以便使用先序遍历遍历树时按正确顺序访问节点。 - GCon

无法编译。节点不能包含自身的实例。sizeof（struct testNode）会是多少？Sizeof（struct Testnode）？2 * sizeof（testNode）+ sizeof（int）？ - wildplasser

@wildplasser，你得原谅我，我已经做了将近5个小时了。leftChild和rightChild实际上是指针。 - GCon

Answer 1

考虑预先排序的BST的定义：根节点是最小元素，并且其两个子节点也是预先排序的树，使得右子树的根比左子树中的任何值都大。

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

1. 如果新节点比根节点小，则将其作为新的根节点，并指向现有树作为两个子节点之一。 2. 如果新节点比根节点大，但比右子树的根节点小，则递归地将其插入到左子树中。 3. 否则，递归地将其插入到右子树中。

这可能不会产生非常平衡的树，但它应该能够工作。我可以想到至少另外一种简单的替代方案，肯定还有办法让事情更平衡，留给读者做练习。

- Yaniv

---

我建议你先休息一下，不要碰电脑。首先用铅笔和纸画些图形。如果你递归地定义问题，只需要两个条件：初始化和归纳。结果很简单：要么替换根节点（“pushdown”），要么替换左子树或右子树，或者进行递归。在动手敲键盘之前，先画出来！ - wildplasser

@wildplasser，我正在画图 :) 感谢您的建议。我已经实现了3个条件：如果小于RC->key，则将其推入，插入（node->left），否则插入（node->right）。由于睡眠不足可能会影响我的判断力，我正在试图用笔和纸弄清楚当节点中缺少子节点时会发生什么？我无法进行比较以决定在哪里插入。我应该检查LC / RC是否缺失并在那里插入吗？ - GCon

当你开始递归思考时，一个丢失的子节点与一个空的根节点并没有什么不同。（在这两种情况下，“推入”一个NULL节点/指针都不会造成任何伤害） - wildplasser

@GCon：对我来说，一个预排序树插入比中序插入要难，因为仅通过检查当前节点不能获得关于递归的全部必要信息；虽然可能我错了，但在进行正确的递归选择时，似乎无法避免检查子节点。 - Yaniv

这是大学数据结构课程作业的一部分。先序遍历部分已经明确说明了。因此，从技术上讲，这是学术性质的，而不是真实世界的。 - GCon