3.txt

用递归的方法求二叉树的树高

你中间写的有点问题，
我改了一下，可以运行了，也可以计算出树的高度，
你想做的是一个二叉排序树，不允许数字重复，
以－1作为输入结束标志，
不过现在是遇到相同输入时就结束，而且你的树做的好像也不对。



因为这一句啊：
if(p==null) h=0;

你的递归结束条件是p==NULL，
所以即使一个结点的左右子树是空指针你还是要调用一次，返回高度0。



#include<stdio.h>
#include<malloc.h>
#define null 0
int counter=0;
int h,hl,hr;
typedef struct btreenode
{
int data;
struct btreenode  *lchild;
struct btreenode  *rchild;
}bnode;

bnode  *create(int x,bnode *lbt,bnode *rbt)
{
bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
void ins_lchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{
q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
p->lchild=q;
}
}

void ins_rchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
p->rchild=q;
}
}

int max(int a,int b)
{
if(a>b)
return(a);
else
{
if(a<b)
return(b);
else
return(a);
}
}

void high(bnode *p,int& h)
{

if(p==null)
h=0;
else
{
if(p->lchild!=null)
  high(p->lchild,hl);
if(p->rchild!=null)
  high(p->rchild,hr);
h=max(hl,hr)+1;
}

}

void main()
{
bnode *bt,*p,*q;
int x;
printf("Input root:");
scanf("%d",&x);
p=create(x,null,null);
bt=p;
scanf("%d",&x);
while(x!=-1)
{
p=bt;
q=p;
while(x!=p->data&&q!=null)

{
p=q;
if(x<p->data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{
printf("The number is always egxit.");
break;
}


else
if(x<p->data)
ins_lchild(p,x);
else
ins_rchild(p,x);
scanf("%d",&x);
}
p=bt;


high(p,h);
printf("\n");

  printf("h=%d",h); 

}