Question

C语言中的二叉树问题

在二叉树的生成和各种操作的上机实验中，程序运行的结果上，二叉树的结点个数、叶结点个数及树的高度这三个数字大得惊人，应该是哪出了问题，可我就是没看出来QAQ，是用的递归算法，代码和运行结果附上

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
#define maxsize 64
//#define NULL -1

typedef struct node
{
datatype data;
struct node * lchild, * rchild;
} bitree;

bitree * bitr;

bitree *Q[maxsize];
bitree *CREATREE( )
{ char ch ; int front , rear ;
bitree *root , *s ;
root = NULL ; front = 1 ; rear = 0 ;
ch = getchar( ) ;
while ( ch != '#')
{ s = NULL ;
if ( ch != '@' )
{ s = malloc(sizeof(bitree));
s->data = ch ; s->lchild = NULL ;s->rchild =NULL;
}

rear ++;
Q[rear] = s ;
if (rear == 1 ) root = s ;
else
{ if ( s && Q[front] )
if (rear%2==0 ) Q[front]->lchild = s ;
else Q[front]->rchild = s ;
if ( rear%2==1 ) front ++;
}
ch = getchar ( ) ;
}
return (root) ;

}

void InOrder ( bitree *t)
{
if ( t )
{
InOrder ( t->lchild );
printf("\t%c\n", t->data);
InOrder ( t->rchild );
}
}

void PreOrder ( bitree *t )
{
if ( t != NULL )
{
printf("\t%c\n",t->data);
PreOrder ( t->lchild );
PreOrder ( t->rchild );
}
}

void PostOrder ( bitree * t )
{
if ( t != NULL )
{
PostOrder ( t->lchild );
PostOrder ( t->rchild );
printf("\t%c\n",t->data);
}
}

int Count ( bitree *T )
{
if ( T == NULL ) return 0;
else
return 1 + Count ( T->lchild )
+ Count ( T->rchild );
}

int Leaf_Count( bitree *T )
{
if(!T) return 0;
else if(!T->lchild&&!T->rchild)
return 1;
}

int Height ( bitree * T )
{ int m, n ;
if ( T == NULL ) return -1;
else
{ m = Height ( T->lchild );
n = Height ( T->rchild );
return (m > n) ? m+1 : n+1;
}
}

int main()
{ bitree *p;
int n1,n2,h;
p=malloc(sizeof(bitree));
p=CREATREE();
printf("中序遍历为:\n");
InOrder(p);
printf("前序遍历为:\n");
PreOrder(p);
printf("后序遍历为:\n");
PostOrder(p);
printf("结点个数:");
n1=Count(p);
printf("%d\n",&n1);
printf("叶结点个数:");
n2=Leaf_Count(p);
printf("%d\n",&n2);
printf("树的高度:");
h=Height(p);
printf("%d\n",&h);

free(p);
return 0;
}

Answer 1

这代码是你写的？ 粗看了下 巨大的数字 瞄了下代码 你输出int居然用&n1这种。。 你输出的是地址。。 另外leaf函数不严谨 不是每个分支都有return 没运行 没环境。。 有问题请追问

追问

取地址符去掉后结点个数和树的高度数字回复个数了，叶结点个数还是好长一串，还有就是树的高度显示是2，应该是3才对呀。。。。

追答

下午帮你看看 先给你个leaf函数~
int Leaf_Count( bitree *T )
{
/*if(!T) return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return 0;*/
if (T==NULL)
{
return 0;
}else if (T->lchild==NULL && T->rchild==NULL)
{
return 1;
}else
{
return Leaf_Count(T->lchild) + Leaf_Count(T->rchild);
}
}

追问

恩呢，刚运行了下，叶结点个数正确【感谢感谢。。】，可是树的高度还是不对。。。

追答

int Height ( bitree * T )
{
/*int m, n ;
if ( T == NULL )
return -1;
else
{
m = Height ( T->lchild );
n = Height ( T->rchild );
return (m > n) ? m+1 : n+1;
} */
int left, right;
if (T == NULL)
{
return 0;
}
left = Height(T->lchild);
right = Height(T->rchild);
if (left<right)
return right+1;
else
return left+1;
}

追问

运行的时候出现了一个错误

追答

可能你以前的exe没关闭~