C语言：双亲表示法的树转化为孩子兄弟的二叉树，再转化回树_孩子兄弟表示法转换成二叉树代码

空间数据结构上机作业

上机要求：

读取文件中用双亲表达的树，打印出来；然后转化成链表的孩子兄弟的二叉树，打印；然后再转化成树

练习文本TreeByParent.txt附上：
0 10
R 0
A 1
B 1
C 1
D 2
E 2
F 4
G 7
H 7
K 7

DS init code 2024/4/27 by 废柴

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
const char* infilename = "D:\\c practice data\\TreeByParent.txt";
//定义双亲表示的树
typedef struct {
	char ch;
	int  parent;
}PTNode;
//定义孩子兄弟表示法的二叉树
typedef struct BTNode{
	char ch;
	BTNode* fchild;
	BTNode* nsbl;
}BTNode;
//1.从文件中读取文件创建树
PTNode*createPTree(const char* infilename, int* n);
//1.1打印树
void printPTree(PTNode nodes[], int n);
//2.转化为孩子兄弟的二叉树
BTNode* convertToB(PTNode nodes[],int n);
//3.打印二叉树
void printBTree(BTNode* root,int n);
//4.将孩子兄弟二叉树重新变成树
PTNode* recover(BTNode* root, int n);
int main() {
	int n = 0;
	PTNode*nodes= createPTree(infilename, &n);
	BTNode* root = convertToB(nodes, n);
	printf("convert to Binary Tree:\n");
	printBTree(root,n);
	PTNode* tree2 = recover(root, n);
	free(nodes);
	free(root);
	free(tree2);
	return 0;
}
//1.从文件中读取文件创建树
PTNode* createPTree(const char* infilename, int* n) {
	FILE* fp = fopen(infilename, "r");
	if (fp == NULL) {
		printf("file open error\n");
		return NULL;
	}
	char ch = 0;
	fscanf(fp, "%c %d\n", &ch, n);
	PTNode* nodes = (PTNode*)malloc(sizeof(PTNode) * (*n));
	memset(nodes, 0, sizeof(PTNode) * (*n));
	for (int i = 0; i < (*n); i++) {
		char ch;
		int parent;
		fscanf(fp, "%c %d\n", &ch, &parent);
		nodes[i].ch = ch;
		nodes[i].parent = parent-1;
	}
	fclose(fp);
	printPTree(nodes, (*n));
	return nodes;

}
//1.1打印树
void printPTree(PTNode*nodes, int n) {
	for (int i = 0; i < n; i++) {
		printf("%d value:%c parent:%d\n",i, nodes[i].ch, nodes[i].parent);
	}
	return;
}
//2.转化为孩子兄弟的二叉树
BTNode* convertToB(PTNode nodes[], int n) {
	BTNode* tree = (BTNode*)malloc(sizeof(BTNode) * n);
	memset(tree, 0, sizeof(BTNode) * n);
	//创建结点并建立父子关系
	for (int i = 0; i < n; i++) {
		BTNode* temp = &tree[i];
		temp->ch = nodes[i].ch;
		//判断是否是根结点
		if (nodes[i].parent != -1) {
			BTNode* parent = &tree[nodes[i].parent];
			//存储当前结点的parent
			//继续判断是否是fchild
			if (parent->fchild == NULL) {
				parent->fchild = temp;
			}
			else {
				//此时不是第一个孩子，那就要循环找到最后一个哥哥
				BTNode* sibling = parent->fchild;
				while (sibling->nsbl != NULL) {
					sibling = sibling->nsbl;
				}sibling->nsbl = temp;
			}
		}
	}
	//找到根节点返回
	for (int i = 0; i < n; i++) {
		if (nodes[i].parent == -1) {
			return &tree[i];
		}
	}
	return NULL;
}
//3.打印二叉树
void printBTree(BTNode* T ,int n) {
	if (T == NULL) {
		printf("空\n");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d value:%c ", i, T[i].ch);
		if (T[i].fchild != NULL) {
			printf("fchild->%c ", T[i].fchild->ch);
		}
		else printf("fchild->NULL ");
		if (T[i].nsbl != NULL) {
			printf("nsbl->%c\n", T[i].nsbl->ch);
		}
		else printf("nsbl->NULL\n");
	}
	return;
}
//4.将孩子兄弟二叉树重新变成树
PTNode* recover(BTNode* root, int n) {
	PTNode* tree2 = (PTNode*)malloc(sizeof(PTNode) * n);
	memset(tree2, 0, sizeof(PTNode) * n);
	for (int i = 0; i < n; i++) {
		tree2[i].ch = root[i].ch;
	}
	tree2[0].parent = -1;
	for (int i = 0; i < n; i++) {
		if (root[i].fchild != NULL){
		    for (int j = i + 1; j < n; j++) {
				if (root[j].ch == root[i].fchild->ch) {
					tree2[j].parent = i;
				}
				if (root[j].nsbl != NULL) {
					for (int q = j + 1; q < n; q++) {
						if (root[j].nsbl->ch == root[q].ch) {
							tree2[q].parent = tree2[j].parent;
						}
					}
				}
		    }    
		}
	}
	printPTree(tree2, n);
	return tree2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

调试结果

思考：

1.代码并没有实现链表存储形式的二叉树，使用的是顺序存储结构
尝试过的链式存储结构需要依靠同种结构的顺序存储数组来实现，打印也不方便
2.对二叉树重新转化树的方式过于冗长，时间复杂度较高，需要改进

强调：

从树转为二叉树，其逻辑思维是：
（1）是否是根结点
（2）如果不是根结点，那么说明有双亲
（3）找到双亲，双亲是否有fchild
（4）如果没有第一个孩子，当前结点是parent的fchild
（5）如果有第一个孩子，那当前结点是fchild的第几个nsbl
（6）想要找到当前结点的上一个兄弟，必须用while()找到parent已有的最后一个子结点

编程小白，恳请指正（doge）
留个坑：用递归做二叉树转树

下节预告：

哈夫曼编码