1

色属性を持つノードを持つ二分木が与えられます。ツリーには赤いノードと青いノードがあります。

ツリーからすべての青いノードを削除し、赤いノードのみを持つツリーを返しますか?

私はこれを次のように実装しようとしました:

Node stripblue(Node root)
{
    if(root.left != NULL)
      root.left = stripblue(root.left) //is this line correct ? //TODO

    if(root.right != NULL)
       root.right = stripblue(root.right) // is this line correct ? //TODO

     if(root.color == RED)
     return root
}

TODOアルゴリズムの一部を実装することに頭を悩ませています。誰かが私にいくつかのアイデアを与えることができますか?

4

1 に答える 1

0

削除前後の走査順序に制限がなければ書きますが、これは一般的な二分木のノードの削除のように見えます。

Node stripblue(Node root)
{
    if(root == NULL)
        return NULL;
    if(root.color == BLUE)
    {
        Node next_r;
        next_r = search_red(root.left);
        if(next_r == NULL)
            next_r = search_red(root.right);
                if(next_r == NULL)
                    return NULL;
                    //no node is RED

            //TODO:swap the content of next_r and root
            next_r.color = BLUE;
            root.color = RED;
    }
    root.left  = stripblue(root.left);
    root.right = stripblue(root.right);
    return root;
}

whilesearch_red(Node root)は、ルートの下にある最初の RED ノードを見つける関数です。プリオーダー トラバーサルの前後で RED ノードの順序を同じに保ちたい場合search_red(Node root)は、左側の子のプリオーダーで最初のノードを見つけるか、右の子の最初のノード。

于 2013-08-27T02:30:10.223 に答える