数据结构例程——以孩子兄弟链存储的树的高度

数据结构例程——以孩子兄弟链存储的树的高度"/>

数据结构例程——以孩子兄弟链存储的树的高度

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

例: 以孩子-兄弟链作为存储结构，求树的高度

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

#include <stdio.h>
#include <malloc.h>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的子树的最大高度maxp=t->vp;while(p!=NULL){m=TreeHeight(p);if(max<m)max=m;p=p->hp;}return(max+1);}
}int main()
{TSBNode *tree;TreeCreate(tree);printf("Height: %d\n", 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\n", 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\n");}
}