假设二叉树采用二叉链存储结构存储，设计一个算法SonNodes，求出一棵给定二叉树的所有非叶子结点的个数 已知二叉树结构体声明如下： typedef struct node{ ElemType data; struct node *lchild; struct node *rchild; } BTNode; 根据上述要求完成算法中的代码，并将完整代码写在答题框内(二叉树结构体声明无需写到答题框) int SonNodes(BTNode *b){ //补充算法中的代码 }

完整代码如下：

int SonNodes(BTNode *b){
    if(b == NULL || (b->lchild == NULL && b->rchild == NULL)) // 若为空树或为叶子结点，返回0
        return 0;
    else
        return SonNodes(b->lchild) + SonNodes(b->rchild) + 1; // 递归求解左右子树的非叶子结点个数，再加上当前结点
}

算法思路：

对于一棵二叉树，如果为空树或为叶子结点，那么它就没有非叶子结点；如果它有左右子树，则它本身也是一个非叶子结点。因此，我们可以使用递归的方式，对二叉树的左右子树分别求解它们的非叶子结点个数，并将它们的个数相加，加上当前结点，即可得到整棵树的非叶子结点个数。