[树] 求树(孩子链表)的深度 与其他基本操作(严蔚敏《数据结构》6.63)

本文主要是介绍[树] 求树(孩子链表)的深度 与其他基本操作(严蔚敏《数据结构》6.63),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

【题目】对以孩子链表表示的树编写计算树的深度的算法

【答案】

/*-------------------------|6.63 求树的深度         |-------------------------*/
int SubTreeDepth(CTree T, int index) { //序号为index的子树深度int max=-1; //孩子的最大深度int sd; //孩子的深度CNode *p;if (!T.nodes[index].firstchild) return 1; //没有孩子,深度为1for (p=T.nodes[index].firstchild; p; p=p->next) { //遍历该结点的所有孩子sd = SubTreeDepth(T, p->index); //求孩子的深度if (max<sd) max=sd;}return max+1; //孩子的最大深度+1
}
int TreeDepth(CTree T) { return SubTreeDepth(T, T.r);
}

【其他基本操作】

// 树的层序次序+每个结点的度 --> 创建CTree
Status CreateCTreeByLevelDegree(CTree *pT,char *levelstr, int *degree) {CNode *c,*sibling;int parent;int i,cnt;//创建结点for (i=0; i<strlen(levelstr); ++i) {//赋值pT->nodes[i].data = levelstr[i];pT->nodes[i].firstchild = NULL;}pT->n=strlen(levelstr); //个数pT->r=0; //根结点//为孩子找爸爸parent=0; //当前的爸爸i=1; //遍历孩子cnt=0; //已经为parent找到了cnt个孩子while (i<strlen(levelstr)) {if (degree[parent]==0 || cnt==degree[parent]) { //parent没有孩子 || parent的孩子已经全部找到cnt=0;parent++;continue;}cnt++; //为parent找到了一个孩子//创建孩子结点c = (CNode *)malloc(sizeof(CNode)); if (!c) exit(OVERFLOW);c->index = i; //孩子的编号c->next = NULL;if (cnt==1) { //第一个孩子pT->nodes[parent].firstchild = c;} else { //不是第一个孩子for(sibling=pT->nodes[parent].firstchild; sibling->next; sibling=sibling->next) ;sibling->next = c;}i++;}return TRUE;
}
// 先根遍历
void SubPreOrder(CTree T, int index) {CNode *child;visit(T.nodes[index].data);for (child=T.nodes[index].firstchild; child; child=child->next)SubPreOrder(T, child->index);
}
void PreOrder(CTree T) {SubPreOrder(T, T.r);
}

【完整代码】

#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
void visit(TElemType e) {printf("%c", e);
}
#define MAX_TREE_SIZE 100
#define maxSize 50typedef struct CNode{int index; //这个孩子的结点号(注意:在严书中变量名为child)struct CNode *next; //下一个孩子结点
}CNode, *ChildPtr; //孩子结点结构(在严书中名为CTNode)
typedef struct{TElemType data;CNode* firstchild;
}PNode; //双亲结点结构(在严书中,结构名为CTBox)
typedef struct{PNode nodes[MAX_TREE_SIZE];int n,r; //结点数 和 根结点的位置
}CTree; //树结构// 先根遍历
void SubPreOrder(CTree T, int index) {CNode *child;visit(T.nodes[index].data);for (child=T.nodes[index].firstchild; child; child=child->next)SubPreOrder(T, child->index);
}
void PreOrder(CTree T) {SubPreOrder(T, T.r);
}/*-------------------------|6.63 求树的深度         |-------------------------*/
int SubTreeDepth(CTree T, int index) { //序号为index的子树深度int max=-1; //孩子的最大深度int sd; //孩子的深度CNode *p;if (!T.nodes[index].firstchild) return 1; //没有孩子,深度为1for (p=T.nodes[index].firstchild; p; p=p->next) { //遍历该结点的所有孩子sd = SubTreeDepth(T, p->index); //求孩子的深度if (max<sd) max=sd;}return max+1; //孩子的最大深度+1
}
int TreeDepth(CTree T) { return SubTreeDepth(T, T.r);
}// 树的层序次序+每个结点的度 --> 创建CTree
Status CreateCTreeByLevelDegree(CTree *pT,char *levelstr, int *degree) {CNode *c,*sibling;int parent;int i,cnt;//创建结点for (i=0; i<strlen(levelstr); ++i) {//赋值pT->nodes[i].data = levelstr[i];pT->nodes[i].firstchild = NULL;}pT->n=strlen(levelstr); //个数pT->r=0; //根结点//为孩子找爸爸parent=0; //当前的爸爸i=1; //遍历孩子cnt=0; //已经为parent找到了cnt个孩子while (i<strlen(levelstr)) {if (degree[parent]==0 || cnt==degree[parent]) { //parent没有孩子 || parent的孩子已经全部找到cnt=0;parent++;continue;}cnt++; //为parent找到了一个孩子//创建孩子结点c = (CNode *)malloc(sizeof(CNode)); if (!c) exit(OVERFLOW);c->index = i; //孩子的编号c->next = NULL;if (cnt==1) { //第一个孩子pT->nodes[parent].firstchild = c;} else { //不是第一个孩子for(sibling=pT->nodes[parent].firstchild; sibling->next; sibling=sibling->next) ;sibling->next = c;}i++;}return TRUE;
}int main() {
/*6.63测试数据
RABCDEFGHI
3 2 0 1 0 0 3 0 0 0
*/CTree T;char levelstr[50];int num[50];int cnt;scanf("%s", levelstr);for (cnt=0; cnt<strlen(levelstr); cnt++) scanf("%d", &num[cnt]);CreateCTreeByLevelDegree(&T, levelstr, num);PreOrder(T);cnt = SubTreeDepth(T, T.r);printf("\nSubTreeDepth:%d\n", cnt);return 0;
}

这篇关于[树] 求树(孩子链表)的深度 与其他基本操作(严蔚敏《数据结构》6.63)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

postgresql数据库基本操作及命令详解

《postgresql数据库基本操作及命令详解》本文介绍了PostgreSQL数据库的基础操作,包括连接、创建、查看数据库,表的增删改查、索引管理、备份恢复及退出命令,适用于数据库管理和开发实践,感兴... 目录1. 连接 PostgreSQL 数据库2. 创建数据库3. 查看当前数据库4. 查看所有数据库

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加

Linux链表操作方式

《Linux链表操作方式》:本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷