当前位置：首页 > news >正文

《数据结构（C语言版）第二版》第五章-树和二叉树（5.6 树和森林）

news 来源：原创 2024/9/21 20:30:30

5.6 树和森林

C语言：树与二叉树的转换—— 爱吃柚子的梨

cstree1.txt：AB0C0D000
cstree2.txt：EF000
cstree3.txt：GH0IJ0000

在这里插入图片描述

生成的二叉树先序序列： AB#C#D##EF##GH#IJ####
其先序序列为： A B C D E F G H I J
其中序序列为： B C D A F E H J I G
其后序序列为： D C B F J I H G E A

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>#define maxSize 100//树的定义
typedef struct CSNode
{char data;struct CSNode* firstchild;struct CSNode* nextsibling;
}CSNode, * CSTree;//二叉树的定义
typedef struct BTNode
{char data;struct BTNode* lchild;struct BTNode* rchild;
}BTNode, * BTree;//森林定义
typedef struct
{CSTree ct[maxSize]; //ct子树int num;
}Forest;//文件指针
FILE* fp;void CreateBTree(BTree& T);
CSTree CreateCSTree();
BTNode* ExchangeToBTree(CSTree ct);
CSTree ExchangeToCSTree(BTNode* bt);
BTree ForestToBTree(Forest F, int low, int high);
Forest* BTreeToForest(BTNode* root);
void preorder(BTNode* bt);
void inorder(BTNode* bt);
void preorder_cstree(CSTree ct);
void posorder_cstree(CSTree ct);
void preorder_forest(Forest F);
void inorder_forest(Forest F);int main()
{//存储路径定义const char* path[3] = { "C:\\Users\\lenovo\\Desktop\\cstree1.txt" ,"C:\\Users\\lenovo\\Desktop\\cstree2.txt" ,"C:\\Users\\lenovo\\Desktop\\cstree3.txt" };Forest F = { NULL,0 };int length = 3;BTree T = NULL;Forest* fptr = NULL;for (int i = 0; i < length; i++){fopen_s(&fp, path[i], "r");/* fopen_s的返回值errno_t代表错误类型，不同的值代表了不同的错误，例如“0”代表成功执行,“1”代表“不允许执行该操作”等等。第一个参数是文件的二级指针；第二个参数是文件的相对路径；第三个参数打开文件的方式：“r”（只读），“w”（打开一个空文件，并写入数据，如果该文件已有内容则会清除原内容），“a”（该方式用来在原文件内容的后面添加内容。	*/F.ct[i] = CreateCSTree();fclose(fp);printf("\n第%d棵树的先根序列为：", i + 1);preorder_cstree(F.ct[i]);printf("\n第%d棵树的后根序列为：", i + 1);posorder_cstree(F.ct[i]);F.num = i;}printf("\n森林的先序序列为：");preorder_forest(F);printf("\n森林的中序序列为：");inorder_forest(F);printf("\n\n请输入要创建的二叉树的先序序列：");CreateBTree(T);fptr = BTreeToForest(T);printf("\n转化后森林的先序序列为：");preorder_forest(F);printf("\n转化后森林的中序序列为：");inorder_forest(F);return 0;
}//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
void CreateBTree(BTree& T)
{char ch = '\0';ch = getchar();if (ch == '#'){T = NULL;}else{T = (BTree)malloc(sizeof(BTNode));T->data = ch;CreateBTree(T->lchild);CreateBTree(T->rchild);}
}//创建一棵树
/* 要先根据树的图，以及树的存储结构，画出目标树转化为的二叉树图。然后写出该二叉树的先序序列（其中，不存在的结点用0表示。）最后将该二叉树的先序序列输入函数CreateCSTree()中，即可得到该树对应的二叉链表，即创建树的过程完成。因为是针对单棵树，所以得到的二叉链表根结点的右子树一定为空。 */
CSTree CreateCSTree()
{char ch = '\0';fscanf_s(fp, "%c", &ch, 20);/* fscanf_s从文件输入流中读入数据，是格式化读写函数，它读取的对象是磁盘文件。遇到空格和换行时结束。第一个参数为指向文件地址的指针，第二个参数为要读取指定字符集（即读取char型字符），第三个参数表示将读取到的字符保存的在ch变量中，第四个参数表示要读取的内存大小返回值是该函数成功读入的数据数量。 */CSTree CT = NULL;if (ch != '0'){CT = (CSTree)malloc(sizeof(CSNode));CT->data = ch;CT->firstchild = CreateCSTree();CT->nextsibling = CreateCSTree();}return CT;
}//树转换成二叉树
BTNode* ExchangeToBTree(CSTree ct)
{if (ct == NULL)return NULL;else{BTNode* bt = (BTNode*)malloc(sizeof(BTNode));bt->data = ct->data;bt->lchild = ExchangeToBTree(ct->firstchild);bt->rchild = ExchangeToBTree(ct->nextsibling);return bt;}
}//二叉树转换成树
CSTree ExchangeToCSTree(BTNode* bt)
{if (bt == NULL)return NULL;else{CSTree ct = (CSTree)malloc(sizeof(CSNode));ct->data = bt->data;ct->firstchild = ExchangeToCSTree(bt->lchild);ct->nextsibling = ExchangeToCSTree(bt->rchild);return ct;}
}//森林转二叉树
BTree ForestToBTree(Forest F, int low, int high)
{//low为当前指向的树，high为第n棵树的下标n-1if (low > high)return NULL;else{BTree root = ExchangeToBTree(F.ct[low]); //里面有创建结点的语句//二叉树的根即为第一棵树的根，同时二叉树的左孩子是第一棵树根节点的子树森林转化成的二叉树root->rchild = ForestToBTree(F, low + 1, high);//二叉树的右子树是森林其他树转换成的二叉树return root;}
}//二叉树转森林
Forest* BTreeToForest(BTNode* root)
{BTNode* p = root;//森林初始化Forest* F = (Forest*)malloc(sizeof(Forest));BTNode* q = NULL;int i = 0;//统计树的个数//将二叉树转化为森林，核心代码while (p != NULL){q = p->rchild;//先用q指向下一棵树的根节点p->rchild = NULL;//将当前有右孩子的二叉树的右孩子链接断开F->ct[i] = ExchangeToCSTree(p);//将二叉树转化为树printf("\n第%d棵树的先根序列为：", i+1);preorder_cstree(F->ct[i]);printf("\n第%d棵树的后根序列为：", i + 1);posorder_cstree(F->ct[i]);i++;p = q;//将p指向下一棵树}F->num = i;return F;
}//二叉树先序遍历
void preorder(BTNode* bt)
{if (bt != NULL){printf("%c", bt->data);preorder(bt->lchild);preorder(bt->rchild);}
}//二叉树中序遍历
void inorder(BTNode* bt)
{if (bt != NULL){inorder(bt->lchild);printf("%c", bt->data);inorder(bt->rchild);}
}//树的先根遍历 = 二叉树的先序遍历
void preorder_cstree(CSTree ct)
{if (ct != NULL){//先树转二叉树BTNode* bt = ExchangeToBTree(ct);preorder(bt);}
}//树的后根遍历 = 二叉树的中序遍历
void posorder_cstree(CSTree ct)
{if (ct != NULL){//先树转二叉树BTNode* bt = ExchangeToBTree(ct);inorder(bt);}
}//森林先序遍历 = 二叉树的先序遍历
void preorder_forest(Forest F)
{BTree bt = ForestToBTree(F, 0, F.num);preorder(bt);
}//森林中序遍历 = 二叉树的中序遍历
void inorder_forest(Forest F)
{BTree bt = ForestToBTree(F, 0, F.num);inorder(bt);
}

在这里插入图片描述

创建一棵树

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100//树的定义
typedef struct CSNode
{char data;struct CSNode* firstchild;struct CSNode* nextsibling;
}CSNode,*CSTree;//二叉树的定义
typedef struct BiTNode
{char data;struct BiTNode* lchild;struct BiTNode* rchild;
}BiTNode;//存储路径定义
typedef struct
{char path[100];
}Str;//文件指针
FILE* fp;CSTree CreateCSTree();int main()
{CSTree CT = NULL;char ps[] = {"C:\\Users\\lenovo\\Desktop\\cstree1.txt"};fopen_s(&fp, ps, "r");/* fopen_s的返回值errno_t代表错误类型，不同的值代表了不同的错误，例如“0”代表成功执行,“1”代表“不允许执行该操作”等等。第一个参数是文件的二级指针；第二个参数是文件的相对路径；第三个参数打开文件的方式：“r”（只读），“w”（打开一个空文件，并写入数据，如果该文件已有内容则会清除原内容），“a”（该方式用来在原文件内容的后面添加内容。	*/CT = CreateCSTree();return 0;
}//创建一棵树：
/* 要先根据树的图，以及树的存储结构，画出目标树转化为的二叉树图。然后写出该二叉树的先序序列（其中，不存在的结点用0表示。）最后将该二叉树的先序序列输入函数CreateCSTree()中，即可得到该树对应的二叉链表，即创建树的过程完成。因为是针对单棵树，所以得到的二叉链表根结点的右子树一定为空。 */CSTree CreateCSTree()
{char ch = '\0';fscanf_s(fp, "%c", &ch, 20);/* fscanf_s从文件输入流中读入数据，是格式化读写函数，它读取的对象是磁盘文件。遇到空格和换行时结束。第一个参数为指向文件地址的指针，第二个参数为要读取指定字符集（即读取char型字符），第三个参数表示将读取到的字符保存的在ch变量中，第四个参数表示要读取的内存大小返回值是该函数成功读入的数据数量。 */CSTree CT = NULL;if (ch != '\0'){CT = (CSNode*)malloc(sizeof(CSNode));CT->data = ch;CT->firstchild = CreateCSTree();CT->nextsibling = CreateCSTree();}return CT;
}