题目

假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法，求二叉树b中第k层上的结点个数。

代码

#include <iostream>
using namespace std;
//------------------------
#define MaxSize 100
//----------------------
typedef char ElemType;
typedef struct tnode{
	ElemType data;
	struct tnode *lchild,*rchild;
}BTNode;
typedef struct{  //其实这里没用到  
	BTNode* data[MaxSize];
	int top;
}StackBT;
//------------------------
//BTNode *an[MaxSize];
//-----------------------
void InitStack(StackBT &st){ //栈的初始化  
	st.top=-1;
}//--------------------------
void DestroyStack(StackBT st){ //销毁栈  
}//--------------------------
int Push(StackBT &st,BTNode* x){ //入栈  
	if(st.top==MaxSize-1)
	  return 0;
	else{
		st.top++;
		st.data[st.top]=x;
		return 1;
	}
}//--------------------------
int Pop(StackBT &st,BTNode* x){ //出栈  
	if(st.top==-1)
	  return 0;
	else{
		x=st.data[st.top];
		st.top--;
		return 1;
	}
}//-------------------------------
int GetTop(StackBT st,BTNode* &x){ //取栈顶元素  
	if(st.top==-1)
	  return 0;
	else{
		x=st.data[st.top];
		return 1;
	}
}//------------------------------------
int StackEmpty(StackBT st){ //判断栈是否为空  
	if(st.top==-1) return 1;
	else return 0;
}
void DestroyBTree(BTNode *&bt){ //销毁二叉树  
	if(bt!=NULL){
		DestroyBTree(bt->lchild);
		DestroyBTree(bt->rchild);
		delete bt;
	}
}//------------------------------
int BTHeight(BTNode *bt){  //求树高  
	int lchilddep,rchilddep;
	if(bt==NULL) return 0;
	else{
		lchilddep=BTHeight(bt->lchild);
		rchilddep=BTHeight(bt->rchild);
		return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);
	}
}//-------------------------------------
int NodeCount(BTNode *bt){ //求节点  
	int num1,num2;
	if(bt==NULL)
	  return 0;
	else{
		num1=NodeCount(bt->lchild);
		num2=NodeCount(bt->rchild);
		return (num1+num2+1);
	}
}//-----------------------------------------
int LeafCount(BTNode *bt){ //求叶子数  
	int num1,num2;
	if(bt==NULL)
	  return 0;
	else if (bt->lchild==NULL&&bt->rchild==NULL)
	  return 1;
	else{
		num1=LeafCount(bt->lchild);
		num2=LeafCount(bt->rchild);
		return (num1+num2);
	}
}//-------------------------------------------
void DispBTree(BTNode *bt){ //输出二叉树  
	if (bt!=NULL){
		cout<<bt->data;
		if (bt->lchild!=NULL || bt->rchild!=NULL){
			cout<<"(";
			DispBTree(bt->lchild);
			if (bt->rchild!=NULL)
			  cout<<",";
			DispBTree(bt->rchild);
			cout<<")";
		}
	}
}//-----------------------------------------

void CreateBTree(BTNode * &bt,char *str)	//由括号表示串创建二叉链
{	BTNode *St[MaxSize],*p=NULL;
	int top=-1,k,j=0;
	char ch;
	bt=NULL;			//建立的二叉树初始时为空
	ch=str[j];
	while (ch!='\0')	//str未扫描完时循环
	{	switch(ch)
		{
		case '(':top++;St[top]=p;k=1; break;	//为左孩子结点
		case ')':top--;break;
		case ',':k=2; break;	//为右孩子结点
		default:p=new BTNode();
				p->data=ch;p->lchild=p->rchild=NULL;
				if (bt==NULL)	//*p为二叉树的根结点
					bt=p;
				else			//已建立二叉树根结点
				{	switch(k) 
					{
					case 1:St[top]->lchild=p;break;
					case 2:St[top]->rchild=p;break;
					}
				}
		}
		j++;
		ch=str[j];
	}
}//-------------------------------
void LevelCount(BTNode *bt,int n){ //计算第n层的节点树  
	BTNode *p=NULL,*temp[MaxSize];
	//StackBT st;
	//InitStack(st);
	int layer=1,count=0,i=0,m=0,f=0;//初始化层数、本层节点个数  
	p=bt; 
	temp[0]=NULL;
	temp[++i]=p;
	if(n==1 && p!=NULL){ //二叉树不为空，查询根节点个数  
		cout<<1<<endl;
		return ;
	}
	else if(p==NULL){//二叉树为空，查询任意层节点个数  
		cout<<0<<endl;
		return ;
	}
	while(1){//二叉树不为空，查询任意层节点个数  
		if(n==layer){  //找到指定层数，跳出循环； 
			cout<<count<<endl;
			break;
		}
		f=0;//用来记录从m到i的移动距离  
		count=0; //初始化每层节点个数 
		layer++; //记录正在计算哪一层 
		while(m+f!=i){ //temp数组内m+1~i之间存的是上一层节点  
			if(temp[1+m+f]->lchild!=NULL){//若上层节点存在左孩子，这一层节点数+1 
				count++;
			}
			if(temp[1+m+f]->rchild!=NULL){//若上层节点存在右孩子，这一层节点数+1 
				count++;
			}
			f++;   //移到上层下一个节点处，再次进行以上的判断  
		}
		for(int k=0;k<f;k++){ //往temp数组中存入刚刚计算的那一层的节点  
			if(temp[1+m+k]->lchild!=NULL){
				temp[++i]=temp[1+m+k]->lchild;
			}
			if(temp[1+m+k]->rchild!=NULL){
				temp[++i]=temp[1+m+k]->rchild;
			}
		}
		m=m+f; //更新m的数值  
	}
}//----------------------------
void LevelOrder(BTNode *bt){  //按层遍历函数  
	BTNode *p;
	BTNode *qu[MaxSize];
	int front,rear;
	front=rear=0;
	rear++;qu[rear]=bt;
	int i=-1;
	while(front!=rear){
		front=(front+1)%MaxSize;
		p=qu[front];
		cout<<p->data;
		if(p->lchild!=NULL){
			rear=(rear+1)%MaxSize;
			qu[rear]=p->lchild;
		}
		if(p->rchild!=NULL){
			rear=(rear+1)%MaxSize;
			qu[rear]=p->rchild;
		}
	}
}//-------------------------------------
int main(){
	char tree[MaxSize];
	cin>>tree;
	int n;
	cin>>n;
	BTNode *bt;
	CreateBTree(bt,tree);
	//LevelOrder(bt); 
	LevelCount(bt,n);
	DestroyBTree(bt);
	return 0;
}