// 統(tǒng)計(jì)二叉樹的葉子數(shù)和度為2的節(jié)點(diǎn)數(shù).cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//

#include "stdafx.h"
#include <iostream>
using namespace std;
struct BiTNode
{
	BiTNode *lchild;
	BiTNode *rchild;
	char data;
};
int CreateBiTree(BiTNode * &T)
{   //按先序次序輸入二叉樹中的結(jié)點(diǎn)的值(一個(gè)字符)，空格字符表示空樹。
	char ch;
    ch=cin.get();
	if(ch==' ') T=NULL;
	else
	{
		T=new BiTNode;
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return 1;
}

int BiTTowleaf(BiTNode *T,int & a)
{  //返回樹中度為二的結(jié)點(diǎn)數(shù),以引用的方式，數(shù)目保存在引用變量a中
	if(T)
	{
	    if(T->lchild!=NULL && T->rchild!=NULL)
					a++;
	    if(BiTTowleaf(T->lchild,a))
			if(BiTTowleaf(T->rchild,a))
			    return 1;
		return 0;
	}
	else
		return 1;
}
int BiTLeafCount(BiTNode* T,int &n)
{   //返回樹的葉子結(jié)點(diǎn)數(shù)
	if(T)
	{
	    if(BiTLeafCount(T->lchild,n))
		    if(BiTLeafCount(T->rchild,n))
			{
			    n++;
				return 1;
			}
		return 0;
	}
	else
		return 1;
}

int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"請(qǐng)按先序順序依次輸入樹的各個(gè)結(jié)點(diǎn)："<<endl;
	BiTNode * T;
	CreateBiTree(T);
	int a,b;
	BiTTowleaf(T,a);
	BiTLeafCount(T,b);
	cout<<endl<<"度的二的結(jié)點(diǎn)個(gè)數(shù)為： "<<a;
	cout<<endl<<"葉子結(jié)點(diǎn)個(gè)數(shù)為：    "<<b;
	cin>>a;


	return 0;
}