[树] 以广义表的形式输出树（孩子兄弟链表CSTree）（严蔚敏《数据结构》6.74）

2024-02-13 12:18
文章标签 输出 链表 数据结构 形式 孩子 广义 兄弟 严蔚敏 cstree 6.74

本文主要是介绍[树] 以广义表的形式输出树（孩子兄弟链表CSTree）（严蔚敏《数据结构》6.74），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

【题目】6.74
试写一递归算法，以6.73题给定的树的广义表表示法的字符序列形式输出以孩子-兄弟链表表示的树

【答案】

/*-----------------------------------------|6.74 以广义表的形式输出                 |-----------------------------------------*/
void PrintAsGList(CSTree T) {CSNode *child;visit(T->data);if (T->firstchild) { //有孩子printf("(");for (child=T->firstchild; child->nextsibling; child=child->nextsibling) {PrintAsGList(child);printf(",");}PrintAsGList(child);printf(")");}
}

【完整答案】

/*-------------------|树-孩子兄弟表达法 |-------------------*/
#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);
}
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];
}/*---------------------------------|6.67 二元组(F,C)创建CSTree      |---------------------------------*/
#define maxSize 50
Status CreateCSTreeByDuplet(CSTree *pT) {char input[5];CSNode *queue[maxSize];int front,rear;CSNode *p, *q;front=rear=0; //对队列初始化for (scanf("%s", input); input[1]!='^'; scanf("%s", input)) {//创建结点p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);p->data=input[1];p->firstchild=p->nextsibling=NULL;//入队列queue[rear]=p;rear=(rear+1)%maxSize;//找爸爸if (input[0]=='^') { //根结点-->不需要找爸爸*pT = p; //传出去} else {for (q=queue[front]; q->data!=input[0]; front=(front+1)%maxSize,q=queue[front]) ; //找爸爸//找哥哥if (!q->firstchild) q->firstchild=p; //它是最大的else { //它不是最大的for(q=q->firstchild; q->nextsibling; q=q->nextsibling) ; //找最近的哥哥q->nextsibling = p; //和哥哥牵手}}}return OK;
}/*-----------------------------------------|6.68 层次序列+每个结点的度-->构造CSTree |-----------------------------------------*/
CSTree CreateCSTreeByLevelDegree(char *levelstr, int *num) {int cnt,i,parent;CSNode *p;CSNode *tmp[maxSize];//先创建结点for (i=0; i < strlen(levelstr); ++i) {p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);p->data = levelstr[i];p->firstchild=p->nextsibling=NULL;tmp[i]=p;}//连接parent=0; //孩子的爸爸cnt=0; //计数器：表示已经找了几个孩子i=1; //遍历结点，为他们找爸爸while (i<strlen(levelstr)) {if (num[parent]==0 || cnt==num[parent]) { //这个父亲没有孩子 || parent的孩子已经找完了cnt=0; //计数器归0parent++; //位移一位continue;}//这个父亲有孩子（i是parent的孩子）cnt++;if (cnt==1) { //i是parent的第一个孩子tmp[parent]->firstchild = tmp[i];} else { //不是第一个孩子tmp[i-1]->nextsibling = tmp[i]; //它是前面的兄弟}i++;}return tmp[0];
}/*-----------------------------------------|6.71 以树状的形式输出                   |-----------------------------------------*/
void PrintAsTree(CSTree T,int i) {/*思路：1. 观察题目输出的序列ABEFCGD2. 此为树的先根遍历-->对应为二叉树存储的先序遍历3. 前面的空格是该结点所在的层数*/int cnt;if (T) {//输出空格for (cnt=1; cnt<i; cnt++) printf(" ");//输出字符visit(T->data);printf("\n");PrintAsTree(T->firstchild, i+1);PrintAsTree(T->nextsibling, i);}
}/*-----------------------------------------|6.73 用广义表的形式构造                 |-----------------------------------------*/
Status CreateCSTreeByGList(CSTree *pT) {char c;while (1) {c = getchar();if (c>='A' && c<='Z') { //根结点*pT = (CSNode *)malloc(sizeof(CSNode)); if (!*pT) exit(OVERFLOW);(*pT)->data = c; (*pT)->firstchild=(*pT)->nextsibling=NULL;} else if (c=='(') { //是我的第一个孩子CreateCSTreeByGList(&(*pT)->firstchild);} else if (c==',') { //是我的兄弟CreateCSTreeByGList(&(*pT)->nextsibling);break; //这里要返回} elsebreak;}return OK;
}/*-----------------------------------------|6.74 以广义表的形式输出                 |-----------------------------------------*/
void PrintAsGList(CSTree T) {CSNode *child;visit(T->data);if (T->firstchild) { //有孩子printf("(");for (child=T->firstchild; child->nextsibling; child=child->nextsibling) {PrintAsGList(child);printf(",");}PrintAsGList(child);printf(")");}
}int main() {
/*6.74测试数据
A(B(E,F),C(G),D)
*/CSTree CST;CreateCSTreeByGList(&CST); //6.73PrintAsGList(CST); //6.74return 0;
}

这篇关于[树] 以广义表的形式输出树（孩子兄弟链表CSTree）（严蔚敏《数据结构》6.74）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/705510。

相关文章

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

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

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

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代，文本到语音（Text-to-Speech, TTS）技术已成为人机交互的关键桥梁，无论是为视障人士提供辅助阅读，还是为智能助手注入声音的灵魂，TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术，再到现今的深度学习解决方案，TTS 技术经历了一段长足的进步。这篇文章将带您穿越时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2