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

Question

我有一个问题，我知道如何像这样计算树中的所有节点 return 1 + rightchild(tree->right) + rightchild(tree->left); 现在我的问题是如果一个节点在该节点中有任何子节点，我将如何计算，图像来展示我正在尝试做的事情。

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

您应该计算当前节点中的子节点数，并将子节点的子节点数加到其中。

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;
}