例6_3.cpp

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

#include<iostream.h>
//查二叉树指定结点的层数
typedef int elemtype;
struct  bitree
{  
  elemtype data;
   bitree *lchild,*rchild;
};
 int p,x;
 bitree *create()
{  bitree *q[100]; //定义q数组作为队列存放二叉链表中结点，100为最大容量
 bitree *s;   //二叉链表中的结点
bitree *root ;   //二叉链表的根指针 
int front=1,rear=0;           //定义队列的头、尾指针
  int ch;                //结点的data域值
  root=NULL;
   cout<<"请按完全二叉树输入结点值（不存在的结点用‘，’表示，‘#’表示结束"<<endl;
  cin>>ch;
  while(ch!=-1)     //输入值为#号,算法结束
  { s=NULL;
    if(ch!=0)       //输入数据不为逗号,表示不为虚结点,否则为虚结点
	{ 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   traver (bitree  *t,  int   lev)
{        if  (t!=NULL){lev++;
          if (t->data==x)    p=lev;
           else
           {traver(t->lchild,lev);              //在左子树中查找
                if  ( p==0)
                 traver (t->rchild,lev);              //在右子树中查找
    }
        }
}
int    level(bitree    *t,       int   x)
//在以T为根的二叉树链表中,找值为X 的结点所在层数
{    p=0;

  traver(t,0);
     return    p;
}


void main()
{ bitree *t;
  t=create();
 cout<<"请输入指定的结点"<<endl;
 cin>>x;
  int y=level(t,x);
  cout<<x<<"所在的层数为："<<y<<endl;
 
}