-2

2つのポインターを持つNodeクラスに基づいて、一般的なツリーを作成しました。nextはノードの長男を指し、brosはノードの次の兄弟を指します。各ノードには容量（int）があり、各リーフは1つの需要単位と見なされます。目標は、ツリーが需要をサポートするかどうかを示すことです（つまり、ツリーの各ブランチには、すべての需要を供給するのに十分な容量があります）。

ツリー構築部分は非常にうまく機能しますが、サプライヤと再帰関数に欠けているバグがあるようです。一般的な説明：isSupplier（node）-ノードがそのブランチの下のすべてのリーフをサポートするのに十分な容量を持っていることを確認します。canDemandBeAnswered（node）-リーフが上に向かって始まるすべてのノードに対してisSupplierを呼び出すことになっている再帰関数。

問題は、再帰が最初のリーフに遭遇した後、それが未知のノードでスタックすることです（ノードがリーフの場合、再帰は呼び出されないため、高さ1で息子がゼロになることは不可能です！）

うまくいけば、誰かが私が逃したものを見つけることができます、ありがとう！

        // This method checks if this node can supply all of its leafs.

    bool isSupplier()
    {
        if ( this->isLeaf() ) { return 1;}
        else 
        {
            this->num_of_leafs = this->Count_Leafs();
            Node* iter = this->next;
            while ( (iter != NULL) )
            {
                if ( iter->isLeaf() == 0 ) 
                { this->num_of_leafs += iter->num_of_leafs; }
                iter = iter->bros;
            }
        }
        if (this->capacity < this->num_of_leafs) { return 0; }
        else { return 1; }
    }

     bool canDemandBeAnswered(Node* root)
    {
        cout << "Height: " << root->getHeight() << " , sons: " << root->Count_Sons() << " ,bros: " << root->getNumBros() << " ,leafs: " << root->getNumLeafs() << " \n";
        if ( root->isLeaf() ) { return 1; }
        Node* iter = root->next;
        while ( iter != NULL )
        {
            canDemandBeAnswered(iter);
            iter->getNextBro();
        }
        return root->isSupplier();
    };

ツリーの作成と再帰呼び出し：

    Node* s8 = new Node(8);
Node* s5 = new Node(5);
Node* s6 = new Node(6);
for(int i=0; i < 2 ; i++){
    s6->addChild(new Node());      
}

Node* s7 = new Node(7);
Node* s2 = new Node(2);
for(int i=0; i < 3 ; i++){
    s2->addChild(new Node());
}

Node* s3 = new Node(3);
Node* s2_2 = new Node(2);  
s2_2->addChild(new Node());

Node* s4 = new Node(4);
 for(int i=0; i < 5 ; i++){
    s4->addChild(new Node());
}

Node* s1 = new Node(1);
 for(int i=0; i < 2 ; i++){
    s1->addChild(new Node());      
}
Node* s2_3 = new Node(2);
 for(int i=0; i < 4 ; i++){
    s2_3->addChild(new Node());
}
Node* s2_4 = new Node(2);  
for(int i=0; i < 3 ; i++){
    s2_4->addChild(new Node());
}
s8->addChild(s5);
s8->addChild(s6);    
s5->addChild(s7);
s5->addChild(s2);
s6->addChild(s3);
s6->addChild(s2_2);
s7->addChild(s4);
s7->addChild(s1);
s3->addChild(s2_3);
s3->addChild(s2_4);
cout << "s8 height: " << s8->getHeight() << " , sons: " << s8->Count_Sons() << " , bros: " << s8->getNumBros() << " , num of leaf: " << s8->getNumLeafs() << " \n";
cout << "s5 height: " << s5->getHeight() << " , sons: " << s5->Count_Sons() << " , bros: " << s5->getNumBros() << " , num of leaf: " << s5->getNumLeafs() << " \n";
cout << "s6 height: " << s6->getHeight() << " , sons: " << s6->Count_Sons() << " , bros: " << s6->getNumBros() << " , num of leaf: " << s6->getNumLeafs() << " \n";
cout << "s7 height: " << s7->getHeight() << " , sons: " << s7->Count_Sons() << " , bros: " << s7->getNumBros() << " , num of leaf: " << s7->getNumLeafs() << " \n";
cout << "s2 height: " << s2->getHeight() << " , sons: " << s2->Count_Sons() << " , bros: " << s2->getNumBros() << " , num of leaf: " << s2->getNumLeafs() << " \n";
cout << "s3 height: " << s3->getHeight() << " , sons: " << s3->Count_Sons() << " , bros: " << s3->getNumBros() << " , num of leaf: " << s3->getNumLeafs() << " \n";
cout << "s2_2 height: " << s2_2->getHeight() << " , sons: " << s2_2->Count_Sons() << " , bros: " << s2_2->getNumBros() << " , num of leaf: " << s2_2->getNumLeafs() << " \n";
cout << "s4 height: " << s4->getHeight() << " , sons: " << s4->Count_Sons() << " , bros: " << s4->getNumBros() << " , num of leaf: " << s4->getNumLeafs() << " \n";
cout << "s1 height: " << s1->getHeight() << " , sons: " << s1->Count_Sons() << " , bros: " << s1->getNumBros() << " , num of leaf: " << s1->getNumLeafs() << " \n";
cout << "s2_3 height: " << s2_3->getHeight() << " , sons: " << s2_3->Count_Sons() << " , bros: " << s2_3->getNumBros() << " , num of leaf: " << s2_3->getNumLeafs() << " \n";
cout << "s2_4 height: " << s2_4->getHeight() << " , sons: " << s2_4->Count_Sons() << " , bros: " << s2_4->getNumBros() << " , num of leaf: " << s2_4->getNumLeafs() << " \n";
bool ans = hw4->canDemandBeAnswered(s8);

そして大きなフィナーレ、私のデバッグ出力： ここに画像の説明を入力してください

4

1 に答える 1

2

あなたのループ

while (iter != NULL)
{
    canDemandBeAnswered(iter);
    iter->getNextBro();
}

を変更することはないため、何もしませんiter。

私はあなたが言うつもりだったと思います

iter = iter->getNextBro();

また、再帰呼び出しの戻り値も無視しています。これはおそらく意図したものではありませんが、それが何をするのかが完全には明確ではありません。

于 2013-01-03T16:44:22.320 に答える