例6_2.cpp

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

//求二叉树的高度
#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 treehigh(bitree *t)
{ int h,lh,rh;
if(t==NULL) h=0;
else {
	lh=treehigh(t->lchild);
    rh=treehigh(t->rchild);
	if(lh>=rh) h=lh+1;
	else h=rh+1;
}
return h;
}



void main()
{ bitree *t;
 t=create();
 int y=treehigh(t);
  cout<<"二叉树的高度为："<<y<<endl;
 
}