我创建了一个基于具有 2 个指针的 Node 类的通用树： next 指向节点的第一个 son ， bros 指向节点的下一个兄弟。每个节点都有一个容量（int），每个叶子都被认为是一个需求单位，目标是说树是否支持需求（意味着树的每个分支都有足够的容量来满足所有需求）。
树构建部分工作得很好，但似乎我的供应商和递归函数中缺少一个错误。一般解释： 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);
和大结局，我的调试输出：
