例6_4.cpp

来自「《数据结构（C++描述）》-李根强-源代码」· C++ 代码 · 共 64 行

//求二叉树中叶子结点数目
#include<iostream.h>
typedef char elemtype;
struct  bitree
{  
  elemtype data;
   bitree *lchild,*rchild;
};
int    p=0;
 char x;
 bitree *create()
{  bitree *q[100]; //定义q数组作为队列存放二叉链表中结点，100为最大容量
 bitree *s;   //二叉链表中的结点
bitree *root ;   //二叉链表的根指针 
int front=1,rear=0;           //定义队列的头、尾指针
  char ch;                //结点的data域值
  root=NULL;
  cout<<"请按完全二叉树输入结点值（不存在的结点用‘，’表示，‘#’表示结束"<<endl;
 
  cin>>ch;
  while(ch!='#')     //输入值为#号,算法结束
  { s=NULL;
    if(ch!=',')       //输入数据不为逗号,表示不为虚结点,否则为虚结点
	{ s=new bitree;
	   s->data=ch;
	   s->lchild=NULL;
	   s->rchild=NULL;
	}
	rear++;
	q[rear]=s;    //新结点或虚结点进队         
	if(rear==1) root=s;
	else
	{ if((s!=NULL)&&(q[front]!=NULL))
		  {  if(rear%2==0)  q[front]->lchild=s;     //rear为偶数,s为双亲左孩子
	          else q[front]->rchild=s;}             //rear为奇数,s为双亲右孩子
	 if(rear%2==1) front++;                //出队

	}
	cin>>ch;}
return root;
}

int    leaf  (bitree    *  t,   int    n)
{          if (t!=NULL)
       {if     ((t->lchild==NULL)&&(t->rchild==NULL))
n++;
n=leaf(t->lchild,n);
n=leaf(t->rchild,n);
}
return  n;
}


void main()
{ bitree *t;
 t=create();
 x=0;
  int y=leaf(t,x);
  cout<<"叶子数目为："<<y<<endl;
 
}