我从一本有关c ++的书中获得了这项具有挑战性的练习，但不确定如何解决此问题。我必须定义一个函数treeNodeCount()，该函数返回二叉树中的节点数（很容易），我还必须定义一个重载函数，该函数需要一个int（0,1或2）来表示子代数目，并且函数应返回具有该特定数量的子代的节点。treeNodeCount都应该使用一个称为的函数nodeCount(elemType root)来对节点进行计数（因此，基本上所有的工作）。
挑战一说，我可以添加第二个参数，nodeCount该参数将要计算的节点的子代数作为参数。
第二个挑战说我们不能使用第二个参数（这是困难的部分）
我能够挑战一个，这就是我的想法：
template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p, int a ) const
{
if (p == NULL){
return 0;
}
else if (a == 0 && p->lLink == NULL && p->rLink == NULL){
return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
else if (a == 1 && (p->lLink != NULL ^ p->rLink != NULL)){
return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
else if (a == 2 && p->lLink != NULL && p->rLink != NULL){
return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
else if (a == -1){
return nodeCount(p->lLink, a) + nodeCount(p->rLink, a) + 1;
}
return nodeCount(p->lLink, a) + nodeCount(p->rLink, a);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount(int a) const{
return nodeCount(root, a);
}
这似乎工作正常，但我坚信必须有更好的方法。虽然我无法进行挑战2，但我也不知道该怎么办（甚至有可能）
您可以通过实现一个函数来返回给定节点的子代数，从而简化逻辑并使其更加简单明了。
template <class elemType>
int nodeSize(nodeType<elemType>* node) const
{
int count = 0;
if (node->lLink)
++count;
if (node->rLink)
++count;
return count;
}
template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType>* node, int count) const
{
if (node)
{
if (nodeSize(node) == count || count == -1)
return nodeCount(node->lLink, count) + nodeCount(node->rLink, count) + 1;
return nodeCount(node->lLink, count) + nodeCount(node->rLink, count);
}
return 0;
}
对于第二个挑战，您需要一个堆栈来避免递归。
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount(int count) const
{
stack<nodeType<elemType>*> node_stack;
node_stack.push(root);
int num_matches = 0;
while (!stack.empty())
{
nodeType<elemType>* node = node_stack.top();
node_stack.pop();
if (node)
{
if (nodeSize(node) == count || count == -1)
++num_matches;
node_stack.push(node->lLink);
node_stack.push(node->rLink);
}
}
return num_matches;
}
编辑：修复了上述递归版本中的问题。感谢David Rodriguez指出这一点。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句