0

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

};
4

1 に答える 1

0

あなたのコードで：

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

新しいノードが割り当てられるたびに、その親は常に NULL です。

ツリーに挿入された最初のノードについては、上記で問題ありません。ただし、左側または右側に挿入する場合は、t->leftまたはt->rightが NULL かどうかを確認する必要があります。NULL の場合、そこに新しいノードを割り当てます。

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

同様に、右側の挿入についても同様です。

于 2013-11-07T04:30:55.773 に答える