频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
数据结构例程——以孩子兄弟链存储的树的高度
2015-10-20 15:34:39         来源:迂者-贺利坚的专栏  
收藏   我要投稿

本文是数据结构基础系列(6):树和二叉树中第5课时树的存储结构的例程。

例: 以孩子-兄弟链作为存储结构,求树的高度
这里写图片描述

源程序:【说明——函数TreeCreate仅创建了如上图所示的图,不具有通用性。】

#include 
#include 

typedef char ElemType;
typedef struct tnode
{
    ElemType data;  //节点的值
    struct tnode *hp;   //指向兄弟
    struct tnode *vp;   //指向孩子节点
} TSBNode;
int TreeHeight(TSBNode *t);
void TreeCreate(TSBNode *&t);
void TreeDisp(TSBNode *t);

int TreeHeight(TSBNode *t)
{
    TSBNode *p;
    int m, max = 0;
    if(t==NULL)
        return(0);
    else if(t->vp==NULL)
        return(1);
    else
    {
        //求t的子树的最大高度max
        p=t->vp;
        while(p!=NULL)
        {
            m=TreeHeight(p);
            if(maxhp;
        }
        return(max+1);
    }
}

int main()
{
    TSBNode *tree;
    TreeCreate(tree);
    printf(Height: %d
, TreeHeight(tree));
    TreeDisp(tree);
    return 0;
}

void TreeCreate(TSBNode *&t)
{
    //本例仅建造说明中特定的树,以支持演示
    TSBNode *a, *b, *c, *d, *e, *f, *g;
    a = (TSBNode *)malloc(sizeof(TSBNode));
    b = (TSBNode *)malloc(sizeof(TSBNode));
    c = (TSBNode *)malloc(sizeof(TSBNode));
    d = (TSBNode *)malloc(sizeof(TSBNode));
    e = (TSBNode *)malloc(sizeof(TSBNode));
    f = (TSBNode *)malloc(sizeof(TSBNode));
    g = (TSBNode *)malloc(sizeof(TSBNode));
    a->data = 'a';
    b->data = 'b';
    c->data = 'c';
    d->data = 'd';
    e->data = 'e';
    f->data = 'f';
    g->data = 'g';
    a->vp = b;
    a->hp = NULL;
    b->vp = d;
    b->hp = c;
    c->vp = NULL;
    c->hp = NULL;
    d->vp = NULL;
    d->hp = e;
    e->vp = g;
    e->hp = f;
    f->vp = NULL;
    f->hp = NULL;
    g->vp = NULL;
    g->hp = NULL;
    t=a;  //a作为根
    return;
}

void TreeDisp(TSBNode *t)
{
    if(t!=NULL)
    {
        printf(node value: %c
, t->data);
        printf(%c's first child --> , t->data);
        TreeDisp(t->hp);
        printf(%c's brother(its father's another child) --> , t->data);
        TreeDisp(t->vp);
    }
    else
    {
        printf(NULL
);
    }
}

 

点击复制链接 与好友分享!回本站首页
上一篇:数据结构例程——哈夫曼树
下一篇:数据结构之自建算法库——二叉树的链式存储及基本运算
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站