c++ - 在 BST 插入中设置父节点

Question

我的 BST 类有一个插入函数，我正在尝试设置父节点，但我遇到了一些麻烦。这是我的功能：

void BST::insert_node(Play& play, BNode *&t){

    if( t == NULL)
        t = new BNode(play, t, NULL, NULL);

    else if( play < t->play){
        insert_node(play, t->left);

        if (height(t->left) - height(t->right) == 2){

            if( play < t->left->play)
                rotate_with_left_child(t);
            else
                double_rotate_with_left_child(t);

        }
    }
    else if( t->play < play){
        insert_node(play, t->right);

        if(height(t->right) - height(t->left) == 2){

            if( t->right->play < play)
                rotate_with_right_child(t);
            else
                double_rotate_with_right_child(t);

        }
    }
    else
        t->node_height = max(height( t->left ), height( t->right )) + 1;

}

目前，我所有节点的父节点都是 NULL。有人可以帮我弄清楚如何正确设置父节点吗？

这是我的节点结构：

struct BNode {
    Play play;
    BNode * parent;
    BNode * left;
    BNode * right;
    int times_searched;
    int node_height;
    BNode(Play p = Play(), BNode *par = NULL, BNode *lt = NULL, BNode *rt = NULL, int ts = 0, int nh = 0)
    : play(p), parent(par), left(lt), right(rt), times_searched(ts), node_height(nh) {}

};

Answer 1

在您的代码中：

if( t == NULL)
        t = new BNode(play, t, NULL, NULL);
                            ^

每当分配任何新节点时，其父节点始终为 NULL。

对于插入到树中的第一个节点，上面是可以的。但是，插入左侧或右侧时，应检查是否t->left为t->rightNULL。如果为 NULL，则在此处分配新节点。例如

else if( play < t->play){
        if(t->left == NULL)
        {
               t->left = new BNode(play, t, NULL, NULL);
        }
        else
        {
               insert_node(play, t->left);
        }
...

同样，对于右侧插入。