btree.cpp

中序遍历输出二叉树 输出二叉树的叶子树 输出二叉树的节点数

#include<iostream.h>
#include<stdlib.h>
typedef char ElemType;
struct BTreeNode{
	ElemType data;
	BTreeNode *left;
	BTreeNode *right;
};
void CreatBTree(BTreeNode *&BT,char *a){
	const MaxSize=10;
	BTreeNode *s[MaxSize];
	int top=-1;
	BT=NULL;
	BTreeNode *p;
	int k;
	int i=0;
	while(a[i]!='@'){
		switch(a[i]){
		case'(':
			top++;s[top]=p;k=1;
			break;
		case')':
			top--;
			break;
		case',':
			k=2;
			break;
		default:
			p=new BTreeNode;
			p->data=a[i];p->left=p->right=NULL;
			if(BT==NULL)BT=p;
			else{
				switch(k)
				{
				case 1:
					s[top]->left=p;
					break;
				case 2:
					s[top]->right=p;
				}
			}
		}
		i++;
	}
}
int BTreeCount(BTreeNode *BT)
{
	if(BT==NULL)return 0;
	else 
		return BTreeCount(BT->left)+BTreeCount(BT->right)+1;
}
int BTreeLeafCount(BTreeNode *BT)
{
	if(BT==NULL) return 0;
	else if(BT->left==NULL&&BT->right==NULL)return 1;
	else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}
void main(){
	BTreeNode *bt;
	char b[50];
	cout<<"请输入一棵二叉树的广义表字符串:"<<endl;
	cin.getline(b,sizeof(b));
    CreatBTree(bt,b);
	cout<<"该二叉树的节点数为:"<<BTreeCount(bt)<<endl;
	cout<<"该二叉树的叶子节点数为:"<<BTreeLeafCount(bt)<<endl;
	
}