[树] 双亲表示法PTree 转 孩子兄弟表达式CSTree(严蔚敏《数据结构》6.66)

本文主要是介绍[树] 双亲表示法PTree 转 孩子兄弟表达式CSTree(严蔚敏《数据结构》6.66),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目来源:严蔚敏《数据结构》C语言版本习题册 6.66

【题目】6.66
假设有n个结点的树T采用了双亲表示法,写出由此建立树的孩子-兄弟链表的算法。

【答案】

/*---------------------------------|6.66 双亲表示法-->孩子兄弟表达式|---------------------------------*/
#define MAX_TREE_SIZE 50typedef struct PTNode{TElemType data;int parent; //双亲的位置域
}PTNode;
typedef struct{PTNode nodes[MAX_TREE_SIZE];int r,n;
}PTree;
CSTree CreateCSTreeByPTree(PTree T) {CSNode *tmp[MAX_TREE_SIZE]; //创建一个辅助的数组,仿照PTree结点的位置存放CSNode *p, *q;int i,parent;if (T.n<=0) return NULL;for (i=0; i<T.n; i++) { //双亲表按层序存储//创建新结点p = (CSNode *)malloc(sizeof(CSNode)); if(!p) exit(OVERFLOW);//赋值p->data = T.nodes[i].data;p->firstchild=p->nextsibling=NULL;//连接parent=T.nodes[i].parent; //父亲if (parent!=-1) { //不是根结点if (tmp[parent]->firstchild==NULL) tmp[parent]->firstchild=p; //第一个孩子else { //不是第一个孩子for (q=tmp[parent]->firstchild; q->nextsibling; q=q->nextsibling) ; //找到最后一个孩子q->nextsibling = p; //连接}}tmp[i]=p;}return tmp[0];
}

【完整代码】

/*-------------------|树-孩子兄弟表达法 |-------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif#define TElemType char
typedef struct CSNode{TElemType data;struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;/*-------------------|6.59 输出T的所有边 |-------------------*/
void TreePrintEdge(CSTree T) {CSNode *p;for (p=T->firstchild; p; p=p->nextsibling) {printf("(%c,%c)\n", T->data, p->data); //输出T的孩子TreePrintEdge(p); //输出p的孩子}
}/*-------------------------|6.60 统计叶子结点的个数 |-------------------------*/
int TreeLeafCnt(CSTree T) {// 树的叶子结点-->没有孩子int ret=0;CSNode *p;if (!T) return 0;else if (!T->firstchild) return 1;else {for (p=T->firstchild; p; p=p->nextsibling) ret += TreeLeafCnt(p);return ret;}
}/*-------------------------|6.61 求树的度           |-------------------------*/
int TreeDegree(CSTree T) {// 最大的孩子数int max=-1;int cnt=0;CSNode *child;if (!T) return -1; //空树else if (!T->firstchild) return 0; //只有一个根结点,度为0else {for (cnt=0,child=T->firstchild; child; child=child->nextsibling) cnt++; //求自己的度max = cnt; //当前的最大值for (child=T->firstchild; child; child=child->nextsibling) {cnt = TreeDegree(child);if (cnt>max) max=cnt;}return max;}
}/*-------------------------|6.62 求树的深度         |-------------------------*/
int TreeDepth(CSTree T) {int h1,h2;if (!T) return 0;else {h1 = TreeDepth(T->firstchild)+1; //T孩子的深度+1h2 = TreeDepth(T->nextsibling); //T兄弟的深度return h1>h2 ? h1 : h2;}
}/*---------------------------------|6.66 双亲表示法-->孩子兄弟表达式|---------------------------------*/
#define MAX_TREE_SIZE 50typedef struct PTNode{TElemType data;int parent; //双亲的位置域
}PTNode;
typedef struct{PTNode nodes[MAX_TREE_SIZE];int r,n;
}PTree;
CSTree CreateCSTreeByPTree(PTree T) {CSNode *tmp[MAX_TREE_SIZE]; //创建一个辅助的数组,仿照PTree结点的位置存放CSNode *p, *q;int i,parent;if (T.n<=0) return NULL;for (i=0; i<T.n; i++) { //双亲表按层序存储//创建新结点p = (CSNode *)malloc(sizeof(CSNode)); if(!p) exit(OVERFLOW);//赋值p->data = T.nodes[i].data;p->firstchild=p->nextsibling=NULL;//连接parent=T.nodes[i].parent; //父亲if (parent!=-1) { //不是根结点if (tmp[parent]->firstchild==NULL) tmp[parent]->firstchild=p; //第一个孩子else { //不是第一个孩子for (q=tmp[parent]->firstchild; q->nextsibling; q=q->nextsibling) ; //找到最后一个孩子q->nextsibling = p; //连接}}tmp[i]=p;}return tmp[0];
}int main() {PTree PT;CSTree CST;PT.n=10;PT.r=0;PT.nodes[0].data='R';PT.nodes[0].parent=-1;PT.nodes[1].data='A';PT.nodes[1].parent=0;PT.nodes[2].data='B';PT.nodes[2].parent=0;PT.nodes[3].data='C';PT.nodes[3].parent=0;PT.nodes[4].data='D';PT.nodes[4].parent=1;PT.nodes[5].data='E';PT.nodes[5].parent=1;PT.nodes[6].data='F';PT.nodes[6].parent=3;PT.nodes[7].data='G';PT.nodes[7].parent=6;PT.nodes[8].data='H';PT.nodes[8].parent=6;PT.nodes[9].data='I';PT.nodes[9].parent=6;CST = CreateCSTreeByPTree(PT);TreePrintEdge(CST);return 0;
}

这篇关于[树] 双亲表示法PTree 转 孩子兄弟表达式CSTree(严蔚敏《数据结构》6.66)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/705507

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

分辨率三兄弟LPI、DPI 和 PPI有什么区别? 搞清分辨率的那些事儿

《分辨率三兄弟LPI、DPI和PPI有什么区别?搞清分辨率的那些事儿》分辨率这个东西,真的是让人又爱又恨,为了搞清楚它,我可是翻阅了不少资料,最后发现“小7的背包”的解释最让我茅塞顿开,于是,我... 在谈到分辨率时,我们经常会遇到三个相似的缩写:PPI、DPI 和 LPI。虽然它们看起来差不多,但实际应用

SpringBoot @Scheduled Cron表达式使用方式

《SpringBoot@ScheduledCron表达式使用方式》:本文主要介绍SpringBoot@ScheduledCron表达式使用方式,具有很好的参考价值,希望对大家有所帮助,如有... 目录Cron 表达式详解1. 表达式格式‌2. 特殊字符解析3. 常用示例‌4. 重点规则5. 动态与复杂场景‌

Spring Boot 集成 Quartz 使用Cron 表达式实现定时任务

《SpringBoot集成Quartz使用Cron表达式实现定时任务》本文介绍了如何在SpringBoot项目中集成Quartz并使用Cron表达式进行任务调度,通过添加Quartz依赖、创... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig