数据结构——计算二叉树中二分结点的个数

方法一：构造一个遍历（层次/中序/先后序应该都可以的），在访问每一个结点时用语句

（b->rchild!=NULL&&b->rchild!=NULL）检查该结点，若满足则全局变量NUM++，最后返回NUM即二分结点数目

//非递归方法
int DsonNode(BiTree T){
	InitQueue(Q);
	BiTree p;
	int NUM=1;//*C语言是否允许这样定义？
	EnQueue(Q,T);
	while(!IsEmpty(Q)){
		DeQueue(Q,p);
		if(p->lchild!=NULL&&p->rchild!=NULL)
			NUM++;
		if(p->lchild!=NULL)
			EnQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);
	}//若一直为NULL则rear不在移动，front不断出队后移最终追上rear则队列空，跳出while
	return NUM;
}

方法二：递归方法

此处记录下对递归的理解

递归中个体即整体（对的个体的操作应与整体的目标相对应），在此处表现为：

①整体：给一棵树的根（输入）求出（返回）该树的二分结点数目

             具体操作：左子树的二分结点总数+右子树的二分结点总数+1

②个体：对某一个结点而言，输入这个结点，返回这个结点为根的树的二分结点总数

构建递归函数时要思考两个问题：1.要返还给上一次层什么

                                                   2.要给下一层什么

在此题中，要返还给上一层【当前结点为根而形成的子树的二分结点数目】，要给下一层【左子/右子】以得到下一层的返还（以左子/右子为根形成的子树的二分结点数目）

int DsonNode(BiTree T){//递归方法
	if(T==NULL)
		return 0;
	else if(T->lchild!=NULL&&T->rchild!=NULL)
		return DsonNode(T->lchild)+DsonNode(T->rchild)+1;//若左右子都存在则返回左子树的数目+右子树数目+该结点本身也是二分结点
	else
		return DsonNode(T->lchild)+DsonNode(T->rchild);//若单分结点则不加该结点本身
}