主题：求树的孩子表示的测试
lt19870917
[专家分：750] 发布于 2006-05-03 22:06:00
#include "stdlib.h"
#include "stdio.h"
#define error 0
#define ok 1
#define max 100
typedef char elemtype;
//树的孩子链表存储表示
typedef struct CTNode{
int child;//孩子在数组中的位置
struct CTNode * next;
}*childptr;//孩子链表头指针
struct CTBox{
elemtype data;//结点数据
childptr firstchild;//孩子链表
};
typedef struct CTree{
CTBox nodes[max+1];//0号不用
int n,r;
}*Tree;
回复列表 （共8个回复）
沙发
lt19870917 [专家分：750] 发布于 2006-05-03 22:07:00
//创建空树???(包含了一个链表)
void inittree(Tree &p)
{
int i;
p=(Tree)malloc(sizeof(CTree));
if(!p) exit(1);
for(i=1;i<=max;i++){
p->nodes[i].data=NULL;
p->nodes[i].firstchild->next=NULL;
}
p->n=0;
p->r=0;
}该函数有误
板凳
lt19870917 [专家分：750] 发布于 2006-05-03 22:09:00
//销毁树
void destroytree(Tree &p)
{
if(!p) return;
free(p);
}
//判断树空
bool emptytree(Tree &p)
{
if(p->n==0) return(1);
return(0);
}
//返回子树深度
int depth(Tree &p,int cur_e)
{
int temp[max],count=0,i,depth_t;
CTNode *k;
k=p->nodes[p->r].firstchild->next;
while(k!=NULL){
temp[count++]=depth(p,k->child);
k=k->next;
}
depth_t=temp[0];
for(i=1;i<count;i++){
if(temp[i]>depth_t)
depth_t=temp[i];
}
return(depth_t+1);
}
//返回根
int root(Tree &p)
{
return(p->r);
}
//返回双亲
int parent(Tree &p,int cur_e)
{
int i;
CTNode *k;
for(i=1;i<=max;i++){
k=p->nodes[i].firstchild->next;
while(k!=NULL){
if(k->child==cur_e)
return(i);
k=k->next;
}
}
return(0);//是根
}
//返回孩子在数组中的位置
int * child(Tree &p,int cur_e,int &count)
{
CTNode *k;
int *child_t,i=0;
count=0;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
count++;
k=k->next;
}
child_t=(int *)malloc(sizeof(int)*count);
if(!child_t) exit(1);
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
child_t[i++]=k->child;
k=k->next;
}
return(child_t);
}
//返回兄弟的位置(同上)采用节约空间的办法
int * sibling(Tree &p,int cur_e,int &count)
{
CTNode *k;
int *sib_t,pare,i=0;
count=0;
pare=parent(p,cur_e);
if(pare==0){
printf("是根,没有兄弟\n");
exit(1);
}
k=p->nodes[pare].firstchild->next;
while(k!=NULL){
if(k->child!=cur_e)
count++;
k=k->next;
}
sib_t=(int *)malloc(sizeof(int)*count);
if(!sib_t) exit(1);
k=p->nodes[pare].firstchild->next;
while(k!=NULL){
if(k->child!=cur_e)
sib_t[i++]=k->child;
k=k->next;
}
return(sib_t);
}
//子树的结点数
int nodes(Tree &p,int cur_e)//cur_e为子树位置
{
int count=1;
CTNode *k;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
count+=nodes(p,k->child);
k=k->next;
}
return(count);
}
3 楼
lt19870917 [专家分：750] 发布于 2006-05-03 22:09:00
//清空子树
void cleartree_n(Tree &p,int cur_e)//cur_e为子树位置
{
CTNode *k;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
cleartree_n(p,k->child);
k=k->next;
}
p->nodes[cur_e].data=NULL;
p->nodes[cur_e].firstchild=NULL;
}
//清空子树
void cleartree_y(Tree &p,int cur_e)
{
p->n-=nodes(p,cur_e);
cleartree_n(p,cur_e);
}
//遍历子树(先根)
void traverse1(Tree &p,int cur_e,void (*visit)(elemtype))//用打印
{
CTNode *k;
visit(p->nodes[cur_e].data);
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
traverse1(p,k->child,visit);
k=k->next;
}
}
//遍历树(后根)
void traverse2(Tree &p,int cur_e,void (*visit)(elemtype))
{
CTNode *k;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
traverse2(p,k->child,visit);
k=k->next;
}
visit(p->nodes[cur_e].data);
}
//visit函数
void print(elemtype p)
{
printf("%c ",p);
}
4 楼
lt19870917 [专家分：750] 发布于 2006-05-04 09:28:00
已测试成功
#include "stdlib.h"
#include "stdio.h"
#define error 0
#define ok 1
#define max 10
typedef char elemtype;
//树的孩子链表存储表示
typedef struct CTNode{
int child;//孩子在数组中的位置
struct CTNode * next;
}*childptr;//孩子链表头指针
struct CTBox{
elemtype data;//结点数据
childptr firstchild;//孩子链表
};
typedef struct CTree{
CTBox nodes[max+1];//0号不用
int n,r;
}*Tree;
//创建空树(包含了一个链表)
void inittree(Tree &p)
{
int i;
p=(Tree)malloc(sizeof(CTree));
if(!p) exit(1);
for(i=1;i<=max;i++)
p->nodes[i].firstchild=(childptr)malloc(sizeof(CTNode));
for(i=1;i<=max;i++){
p->nodes[i].data=NULL;
p->nodes[i].firstchild->next=NULL;
}
p->n=0;
p->r=0;
}
//销毁树
void destroytree(Tree &p)
{
if(!p) return;
free(p);
}
//判断树空
bool emptytree(Tree &p)
{
if(p->n==0) return(1);
return(0);
}
//返回子树深度
int depthtree(Tree &p,int cur_e)
{
int temp[max],count=0,i,depth_t;
CTNode *k;
for(i=0;i<max;i++)
temp[i]=0;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
temp[count++]=depthtree(p,k->child);
k=k->next;
}
depth_t=temp[0];
for(i=1;i<count;i++){
if(temp[i]>depth_t)
depth_t=temp[i];
}
depth_t++;
return(depth_t);
}
//返回根
int root(Tree &p)
{
return(p->r);
}
//返回双亲
int parent(Tree &p,int cur_e)
{
int i;
CTNode *k;
for(i=1;i<=max;i++){
k=p->nodes[i].firstchild->next;
while(k!=NULL){
if(k->child==cur_e)
return(i);
k=k->next;
}
}
return(0);//是根
}
//返回孩子在数组中的位置
int * child(Tree &p,int cur_e,int &count)
{
CTNode *k;
int *child_t,i=0;
count=0;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
count++;
k=k->next;
}
child_t=(int *)malloc(sizeof(int)*count);
if(!child_t) exit(1);
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
child_t[i++]=k->child;
k=k->next;
}
return(child_t);
}
//返回兄弟的位置(同上)采用节约空间的办法
int * sibling(Tree &p,int cur_e,int &count)
{
CTNode *k;
int *sib_t,pare,i=0;
count=0;
pare=parent(p,cur_e);
if(pare==0){
printf("是根,没有兄弟\n");
exit(1);
}
k=p->nodes[pare].firstchild->next;
while(k!=NULL){
if(k->child!=cur_e)
count++;
k=k->next;
}
sib_t=(int *)malloc(sizeof(int)*count);
if(!sib_t) exit(1);
k=p->nodes[pare].firstchild->next;
while(k!=NULL){
if(k->child!=cur_e)
sib_t[i++]=k->child;
k=k->next;
}
return(sib_t);
}
//子树的结点数
int nodes(Tree &p,int cur_e)//cur_e为子树位置
{
int count=1;
CTNode *k;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
count+=nodes(p,k->child);
k=k->next;
}
return(count);
}
//清空子树
void cleartree_n(Tree &p,int cur_e)//cur_e为子树位置
{
CTNode *k,*q;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
cleartree_n(p,k->child);
k=k->next;
}
p->nodes[cur_e].data=NULL;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
q=k;
k=k->next;
free(q);
}
p->nodes[cur_e].firstchild->next=NULL;
}
//清空子树
void cleartree_y(Tree &p,int cur_e)
{
int pare;
CTNode *k,*q;
p->n-=nodes(p,cur_e);
cleartree_n(p,cur_e);
pare=parent(p,cur_e);
if(pare!=0){
q=p->nodes[pare].firstchild;
k=q->next;
while(k!=NULL){
if(k->child==cur_e){
q->next=k->next;
free(k);
break;
}
k=k->next;
q=q->next;
}
}
}
//遍历子树(先根)
void traverse1(Tree &p,int cur_e,void (*visit)(elemtype))//用打印
{
CTNode *k;
visit(p->nodes[cur_e].data);
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
traverse1(p,k->child,visit);
k=k->next;
}
}
//遍历树(后根)
void traverse2(Tree &p,int cur_e,void (*visit)(elemtype))
{
CTNode *k;
k=p->nodes[cur_e].firstchild->next;
while(k!=NULL){
traverse2(p,k->child,visit);
k=k->next;
}
visit(p->nodes[cur_e].data);
}
//visit函数
void print(elemtype p)
{
printf("%c ",p);
}
5 楼
lt19870917 [专家分：750] 发布于 2006-05-04 09:28:00
测试函数为:
void main()
{
Tree t1;
int *c=NULL,*s=NULL,i,num;
CTNode *k;
inittree(t1);
t1->nodes[1].data='A';
t1->nodes[2].data='B';
t1->nodes[3].data='C';
t1->nodes[4].data='D';
t1->nodes[5].data='F';
t1->nodes[6].data='K';
k=(CTNode *)malloc(sizeof(CTNode));
t1->nodes[6].firstchild->next=k;
k->child=5;
k=(CTNode *)malloc(sizeof(CTNode));
t1->nodes[6].firstchild->next->next=k;
k->child=3;
k->next=NULL;
k=(CTNode *)malloc(sizeof(CTNode));
t1->nodes[5].firstchild->next=k;
k->child=4;
k->next=NULL;
k=(CTNode *)malloc(sizeof(CTNode));
t1->nodes[4].firstchild->next=k;
k->child=2;
k->next=NULL;
k=(CTNode *)malloc(sizeof(CTNode));
t1->nodes[3].firstchild->next=k;
k->child=1;
k->next=NULL;
t1->nodes[2].firstchild->next=NULL;
t1->nodes[1].firstchild->next=NULL;
t1->n=6;
t1->r=6;
printf("测试结点数");
printf("t1的nodes:%d\n",nodes(t1,6));
printf("测试子树深度");
printf("t1的depth:%d\n",depthtree(t1,6));
printf("\n测试先根遍历");
traverse1(t1,6,print);
printf("\n测试后根遍历");
traverse2(t1,6,print);
printf("\n测试返回孩子");
c=child(t1,6,num);
for(i=0;i<num;i++)
printf("%c ",t1->nodes[c[i]].data);
printf("\n测试返回兄弟");
s=sibling(t1,5,num);
for(i=0;i<num;i++)
printf("%c ",t1->nodes[s[i]].data);
printf("\n测试删除子树");
cleartree_y(t1,5);
printf("t1的nodes:%d\n",nodes(t1,6));
}
6 楼
lt19870917 [专家分：750] 发布于 2006-05-04 09:36:00
例子:
[img]C:\Documents and Settings\All Users\Documents\My Pictures\示例图片[/img]
7 楼
lt19870917 [专家分：750] 发布于 2006-05-04 09:37:00
[img]http://C:\Documents and Settings\All Users\Documents\My Pictures\示例图片[/img]
8 楼
lt19870917 [专家分：750] 发布于 2006-05-04 09:42:00
[img]C:\Documents and Settings\All Users\Documents\My Pictures\示例图片\未命名.bmp[/img]
我来回复
您所在位置：