计算一个节点在 BST 中是否有 children

Question

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

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

Answer 2

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

计算一个节点在 BST 中是否有 children

Counting if a node has any children in BST

c

recursion

binary-search-tree

children