计算节点在 BST 中是否有任何子节点

Question

我遇到了一个问题，我知道如何计算树中的所有节点，像这样返回 1 个右子（树-

static int rightchild(const treeNode* tree){

    if(tree == NULL){
        return 0;
    }

    if(tree->right !=NULL){
        return 1 + rightchild(tree->right) + rightchild(tree->left);
    }
    else {
        return rightchild(tree->left);
    }

}

static int leftchild(const treeNode* tree){

    if(tree == NULL){
        return 0;
    }

    if(tree->left != NULL){
        return 1 + leftchild(tree->right) + leftchild(tree->left);
    }
    else {
        return leftchild(tree->right);
    }

}

希望我走在正确的道路上，我只是错过了一些东西，我将两个函数的结果结合起来，但它总是不准确的。




Answer 1

MikeCAT的答案是完全正确的，但我想给出另一个观点：计算树中的所有节点，然后从中减去1以计算根。

static int countNodes (treeNode* root) {
    if (root == NULL) return 0;
    return (1 + countNodes (root->left) + countNodes (root->right));
}

static int countChildren (treeNode * root) {
    if (root == NULL) return 0;
    return countNodes (root) - 1;
}

Answer 2

您应该计算当前节点中的子节点数，并将子节点的子节点数之和相加。

static int countchild(const treeNode* tree) {
    int childrenNum = 0;
    if (tree == NULL) {
        return 0;
    }
    if (tree->left != NULL) {
        /* this node has a child in left + add the number of children in the left subtree */
        childrenNum += 1 + countchild(tree->left);
    }
    if (tree->right != NULL) {
        /* this node has a child in right + add the number of children in the right subtree */
        childrenNum += 1 + countchild(tree->right);
    }
    return childrenNum;
}