计算二叉树中具有特定数量 children 的节点？

Question

我从一本关于 c++ 的书中得到了这个具有挑战性的练习，但我不确定如何解决这个问题。我必须定义一个名为 treeNodeCount() 的函数，它 return 是二叉树中的节点数（很简单），而且我还必须定义一个重载函数，它接受一个 int(0,1, or 2) 表示 children 的数量，函数应该 return 具有特定数量 children 的节点。 treeNodeCount 应该都使用一个名为 nodeCount(elemType root) 的函数来执行计算节点所需的递归（所以基本上所有的工作）。

第一个挑战说我可以向 nodeCount 添加第二个参数，它为我们要计算的节点采用 children 的数量。

第二个挑战说我们不能使用第二个参数（这是困难的部分）

我能够完成挑战一，这是我想出的：

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，但我不知道该做什么（甚至可能）

Answer 1

您可以简化您的逻辑并通过实现一个函数来使它更直接一些 return children 给定节点的数量。

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 指出。

计算二叉树中具有特定数量 children 的节点？

Count nodes with specific number of children in a binary tree?

c++

recursion

binary-tree

children

nodes