143-8

二叉树采用二叉链表存储，计算给定二叉树的所有双分支结点个数

递归思想

当根结点不存在左右结点时，return 0；

当根节点存在左右结点时，return Count(T->lchild)+Count(T->rchild)+1;

当根节点只存在一个结点时，return Count(T->lchild)+Count(T->rchild)；

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

int Count(Tree T)
{
    if(T==NULL)
        return 0;
    if(T->lchild&&T->rchild)
        return Count(T->lchild)+Count(T->rchild)+1;    
    else
        return Count(T->lchild)+Count(T->rchild);
} 

int main()
{
    Tree T;
    CreateTree(T);
    printf("双支结点个数为:%d",Count(T));
    
    return 0;
}