例6_6.cpp

《数据结构（C++描述）》-李根强-源代码

#include<iostream.h>
//按层次遍历二叉链表
typedef char elemtype;
struct  bitree
{  
  elemtype data;
   bitree *lchild,*rchild;
};


 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;
}
void  lorder (bitree *t)
{  bitree *q[1000],*p;      
int  f,r;                     // f,r类似于头尾指针
q[1]=t;   f=r=1;
cout<<"层次遍历结果为:";
  while (f<=r)
{   p=q[f];      f++;        //出队
     cout<<p->data<<" ";
     if(p->lchild!=NULL)
      {   r++;  q[r]=p->lchild; } //入队
      if  (p->rchild!=NULL)
     {   r++;      q[r]=p->rchild;}   //入队
  }
  cout<<endl;
    }
void main()
{ bitree *t;
t=create();
lorder(t);
}