注册 登录
编程论坛 数据结构与算法

计算以孩子-兄弟链表示的树的高度

xiaoxxr 发布于 2010-12-09 22:52, 1519 次点击
利用递归的方法计算树高,但是运行结果总是2,是不是在创建的时候出了问题?
程序代码:
#include <stdio.h>
#include <stdlib.h>
typedef char telemtype;
typedef struct tnode{
    telemtype data;
    struct tnode *hp,*vp;}tnode,*bitree;
int visit(bitree p){
    int max=0;
    if(p!=NULL){
        printf("%c ",p->data);
        visit(p->hp);
        visit(p->vp);
    }
    return max;
}
void createbt(bitree &bt){
    char ch;
    scanf("%c",&ch);
    if(ch=='#')bt=NULL;
    else{
        bt=(bitree)malloc(sizeof(tnode));
        bt->data=ch;
        createbt(bt->hp);
        createbt(bt->vp);
    }
}
int height(bitree &bt){
    tnode *p;
    int m,max=0;
    if(bt==NULL)
        return 0;
    else if(bt->vp==NULL)
        return 1;
    else{
        p=bt->vp;
        while(p!=NULL){
            m=height(p);
            if(max<m) max=m;
            p=p->hp;
        }
        return m+1;
    }
}
void main(){
    bitree bt;
    printf("请输入树:");
    createbt(bt);
    printf("树为:\n");
    visit(bt);
    printf("\n树深为%d\n",visit(bt));
}
13 回复
#2
kidangel6662010-12-10 09:53
printf("\n树深为%d\n",height(bt));
你函数都写对了,但是,就是这句写错
#3
寒风中的细雨2010-12-10 16:17
return max+1;

    char ch[2];
    scanf("%s",ch);
    if(ch[0]=='#')
        bt=NULL;
    else
    {
        bt=(bitree)malloc(sizeof(tnode));
        bt->data=ch[0];
        createbt(bt->hp);
        createbt(bt->vp);
    }
#4
xiaoxxr2010-12-10 16:24
为什么它的递归创建和二叉树的不同呢?我运行出来结果都是1啊。。。

[ 本帖最后由 xiaoxxr 于 2010-12-10 16:45 编辑 ]
#5
kidangel6662010-12-10 23:59
恩?你照我那样改还是一?我输入ABD##E##C#F##的时候输出为3,符合结果
#6
xiaoxxr2010-12-11 16:12
哦,貌似是我输入的时候错了,请教一下输入树时的顺序是什么啊?比如:A有三个孩子B、C、D,B又有一个孩子E,我输的是ABE##C#D###
#7
kidangel6662010-12-11 16:21
你建立的是二叉树,哪里出来1个根节点有3个孩子的啊
#8
寒风中的细雨2010-12-11 16:51
采用的存储结构式 孩子兄弟
根据int height(bitree &bt)函数 中的
if(bt==NULL)
        return 0;
else if(bt->vp==NULL)
        return 1;
else{。。。}语句 vp这支表示孩子 则自然hp表示兄弟
根据void createbt(bitree &bt)函数中的
    char ch;
    scanf("%c",&ch);
    if(ch=='#')bt=NULL;
    else{
        bt=(bitree)malloc(sizeof(tnode));
        bt->data=ch;
        createbt(bt->hp);
        createbt(bt->vp);
    }
是先兄弟 后再是孩子 这样 的顺序来构造的
如果有棵树 如下:
            A
       B    C     D
       E    F     G
表示A有三个孩子B C D第三层分别是对应的上层的孩子  则输入为:A # B C D # E # # F # # G # #
只有本站会员才能查看附件,请 登录
#9
寒风中的细雨2010-12-11 16:54
下次写的时候 带点可以看懂点的注释 哪个指向是孩子那个是兄弟 写的时候就不会把握不准
#10
xiaoxxr2010-12-11 16:55
嗯嗯,受教了,谢谢!

[ 本帖最后由 xiaoxxr 于 2010-12-11 16:58 编辑 ]
#11
fp1512010-12-25 23:32
这个是怎么输入的啊????????????谁能解释下吗?
#12
fp1512010-12-25 23:39
这个存储的结构是不是和二叉树是一样的啊??????就是说它转化为二叉树的高度和它本身的高度是一样的吗???????
#13
诸葛修勤2010-12-26 08:00
存储结构和二叉树相同
高度 是树本身的高度 而并非转换后二叉树的高度
#14
fp1512010-12-26 12:34
明白了,懂了
1