GDPU 数据结构 天码行空10

数据结构实验十 树遍历应用

一、【实验目的】

1、了解树的建立方法
2、掌握树与二叉树的转化及其遍历的基本方法
3、掌握递归二叉树遍历算法的应用

二、【实验内容】

1.构造一棵药品信息树,树的形态如下图所示，打印出先序遍历、后序遍历的遍历序列。
2.编写一个层序遍历算法，利用队列结构按层次（同一层自左至右）输出树中所有的结点。
3.将树结构转化为二叉树，编写二叉树非递归中序遍历算法，并输出遍历序列。

三、【实验源代码】

⭐ CPP版

#include 
#include 
#include 

using namespace std;

// 多叉树节点
struct Node {
	string name; // 节点名称
	vector<Node*> nodes; // 子节点指针数组
	
	Node(string name, vector<Node*> nodes) : name(name), nodes(nodes) {}
};

// 二叉树节点
struct BinaryNode {
	string name; // 节点名称
	BinaryNode *left; // 左子节点指针
	BinaryNode *right; // 右子节点指针
	
	BinaryNode(string name, BinaryNode *left, BinaryNode *right) : name(name), left(left), right(right) {}
};

// 按照题意初始化多叉树
Node* init() {
	// 第四层
	Node* n31 = new Node("神经系统用药", {});
	Node* n32 = new Node("消化系统用药", {});
	Node* n33 = new Node("呼吸系统用药", {});
	Node* n34 = new Node("心脑血管系统用药", {});
	Node* n35 = new Node("抗感染药", {});
	Node* n36 = new Node("其他用药", {});
	// 第三层
	vector<Node*> ns1 = {n31, n32, n33, n34, n35, n36};
	Node* n21 = new Node("中成药", {});
	Node* n22 = new Node("化学药品", ns1);
	// 第二层
	vector<Node*> ns2 = {n21, n22};
	Node* n11 = new Node("双规制处方药", ns2);
	Node* n12 = new Node("单规制处方药", {});
	// 第一层
	Node* root = new Node("药品信息", {n11, n12}); // 根节点
	return root;
}

// 队列实现层序遍历
void LevelOrderByQueue(Node* root) {
	queue<Node*> q;
	q.push(root);
	cout << "队列实现层序遍历:" << endl;
	while (!q.empty()) {
		Node* t = q.front(); // 取出队首节点
		q.pop(); // 队首节点出队
		cout << t->name << " "; // 输出节点名称
		for (Node* node : t->nodes) {
			q.push(node); // 将子节点加入队列
		}
	}
}

// 二叉树的非递归遍历(栈)
void InOrder(BinaryNode* root) {
	stack<BinaryNode*> s;
	BinaryNode* t = root;
	cout << endl;
	cout << "二叉树的中序遍历:" << endl;
	while (t != nullptr || !s.empty()) {
		if (t != nullptr) {
			s.push(t);
			t = t->left; // 移动到左子节点
		} else {
			t = s.top(); // 弹出栈顶节点
			s.pop();
			cout << t->name << " "; // 输出节点名称
			t = t->right; // 移动到右子节点
		}
	}
}

// 多叉树转二叉树
void createBinaryTree(Node* root, BinaryNode* broot) {
	if (root == nullptr) {
		return;
	}
	broot->name = root->name; // 转换节点名称
	vector<Node*> nodes = root->nodes;
	if (nodes.empty()) {
		return;
	}
	// 左儿子右兄弟
	BinaryNode* left = new BinaryNode("", nullptr, nullptr);
	createBinaryTree(nodes[0], left); // 递归构建左子树
	BinaryNode* t = left;
	for (int i = 1; i < nodes.size(); i++) {
		Node* node = nodes[i];
		BinaryNode* right = new BinaryNode(node->name, nullptr, nullptr); // 构建右子树
		createBinaryTree(nodes[i], right); // 递归构建右子树
		t->right = right; // 连接右兄弟节点
		t = right;
	}
	broot->left = left; // 连接左子树
}

// 多叉树的先序遍历
void preOrder(Node* root) {
	if (root == nullptr) {
		return;
	}
	cout << root->name << " "; // 输出节点名称
	for (Node* n : root->nodes) {
		preOrder(n); // 递归遍历子节点
	}
}

// 多叉树的后序遍历
void postOrder(Node* root) {
	if (root == nullptr) {
		return;
	}
	for (Node* n : root->nodes) {
		postOrder(n); // 递归遍历子节点
	}
	cout << root->name << " "; // 输出节点名称
}

int main() {
	Node* root = init();
	// 打印先后序遍历
	cout << "多叉树的先序遍历:" << endl;
	preOrder(root); // 先序遍历
	cout << "\n多叉树的后序遍历:" << endl;
	postOrder(root); // 后序遍历
	cout << endl;
	LevelOrderByQueue(root); // 层序遍历
	BinaryNode* broot = new BinaryNode("", nullptr, nullptr);
	createBinaryTree(root, broot); // 多叉树转二叉树
	InOrder(broot); // 中序遍历二叉树
	return 0;
}
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

⭐ c语言版

#include 
#include 

// 多叉树节点
typedef struct Node
{
	char* name;
	struct Node** nodes;
	int numOfNodes;
} Node;

// 二叉树节点
typedef struct BinaryNode
{
	char* name;
	struct BinaryNode* left;
	struct BinaryNode* right;
} BinaryNode;

// 按照题意初始化多叉树
Node* init()
{
	// 第四层
	Node* n31 = (Node*)malloc(sizeof(Node));
	n31->name = "神经系统用药";
	n31->nodes = NULL;
	n31->numOfNodes = 0;
	
	Node* n32 = (Node*)malloc(sizeof(Node));
	n32->name = "消化系统用药";
	n32->nodes = NULL;
	n32->numOfNodes = 0;
	
	Node* n33 = (Node*)malloc(sizeof(Node));
	n33->name = "呼吸系统用药";
	n33->nodes = NULL;
	n33->numOfNodes = 0;
	
	Node* n34 = (Node*)malloc(sizeof(Node));
	n34->name = "心脑血管系统用药";
	n34->nodes = NULL;
	n34->numOfNodes = 0;
	
	Node* n35 = (Node*)malloc(sizeof(Node));
	n35->name = "抗感染药";
	n35->nodes = NULL;
	n35->numOfNodes = 0;
	
	Node* n36 = (Node*)malloc(sizeof(Node));
	n36->name = "其他用药";
	n36->nodes = NULL;
	n36->numOfNodes = 0;
	
	// 第三层
	Node** ns1 = (Node**)malloc(6 * sizeof(Node*));
	ns1[0] = n31;
	ns1[1] = n32;
	ns1[2] = n33;
	ns1[3] = n34;
	ns1[4] = n35;
	ns1[5] = n36;
	
	Node* n21 = (Node*)malloc(sizeof(Node));
	n21->name = "中成药";
	n21->nodes = NULL;
	n21->numOfNodes = 0;
	
	Node* n22 = (Node*)malloc(sizeof(Node));
	n22->name = "化学药品";
	n22->nodes = ns1;
	n22->numOfNodes = 6;
	
	// 第二层
	Node** ns2 = (Node**)malloc(2 * sizeof(Node*));
	ns2[0] = n21;
	ns2[1] = n22;
	
	Node* n11 = (Node*)malloc(sizeof(Node));
	n11->name = "双规制处方药";
	n11->nodes = ns2;
	n11->numOfNodes = 2;
	
	Node* n12 = (Node*)malloc(sizeof(Node));
	n12->name = "单规制处方药";
	n12->nodes = NULL;
	n12->numOfNodes = 0;
	
	// 第一层
	Node* root = (Node*)malloc(sizeof(Node));
	root->name = "药品信息";
	root->nodes = (Node**)malloc(2 * sizeof(Node*));
	root->nodes[0] = n11;
	root->nodes[1] = n12;
	root->numOfNodes = 2;
	
	return root;
}

// 队列实现层序遍历
void LevelOrderByQueue(Node* root)
{
	Node** queue = (Node**)malloc(1000 * sizeof(Node*));
	int front = 0;
	int rear = 0;
	
	queue[rear++] = root;
	
	printf("队列实现层序遍历:\n");
	while (front < rear)
	{
		Node* t = queue[front++];
		printf("%s ", t->name);
		
		if (t->nodes != NULL)
		{
			for (int i = 0; i < t->numOfNodes; i++)
			{
				queue[rear++] = t->nodes[i];
			}
		}
	}
	
	free(queue);
}

// 二叉树的中序遍历(栈)
void InOrder(BinaryNode* root)
{
	BinaryNode** stack = (BinaryNode**)malloc(1000 * sizeof(BinaryNode*));
	int top = -1;
	
	BinaryNode* t = root;
	
	printf("\n二叉树的中序遍历:\n");
	// 中序：先输出左子树，再输出根，只要左子树非空，就一直把左子树入栈
	while (t != NULL || top != -1)
	{
		if (t != NULL)
		{
			stack[++top] = t;
			t = t->left;
		}
		else
		{
			t = stack[top--]; // 说明当前栈顶元素的左子树为空，可以输出栈顶元素
			printf("%s ", t->name);
			t = t->right; // 根输出后，接着继续遍历右子树
		}
	}
	
	free(stack);
}

// 多叉树转二叉树
BinaryNode* createBinaryTree(Node* root, BinaryNode* broot)
{
	if (root == NULL)
		return NULL;
	
	broot->name = root->name;
	Node** nodes = root->nodes;
	
	if (nodes == NULL)
		return NULL;
	
	// 左儿子右兄弟
	BinaryNode* left = (BinaryNode*)malloc(sizeof(BinaryNode));
	createBinaryTree(nodes[0], left);
	
	BinaryNode* t = left;
	for (int i = 1; i < root->numOfNodes; i++)
	{
		Node* node = nodes[i];
		BinaryNode* right = (BinaryNode*)malloc(sizeof(BinaryNode));
		createBinaryTree(nodes[i], right);
		t->right = right;
		t = right;
	}
	
	broot->left = left;
	
	return broot;
}

// 多叉树的先序遍历
void preOrder(Node* root)
{
	if (root == NULL)
		return;
	
	printf("%s ", root->name);
	
	Node** nodes = root->nodes;
	if (nodes == NULL)
		return;
	
	for (int i = 0; i < root->numOfNodes; i++)
	{
		preOrder(nodes[i]);
	}
}

// 多叉树的后序遍历
void postOrder(Node* root)
{
	if (root == NULL)
		return;
	
	Node** nodes = root->nodes;
	if (nodes == NULL)
	{
		printf("%s ", root->name);
		return;
	}
	
	for (int i = 0; i < root->numOfNodes; i++)
	{
		postOrder(nodes[i]);
	}
	
	printf("%s ", root->name);
}

int main()
{
	Node* root = init();
	
	// 打印先后序遍历
	printf("多叉树的先序遍历:\n");
	preOrder(root);
	printf("\n多叉树的后序遍历:\n");
	postOrder(root);
	printf("\n");
	
	LevelOrderByQueue(root);
	
	BinaryNode* broot = (BinaryNode*)malloc(sizeof(BinaryNode));
	createBinaryTree(root, broot);
	InOrder(broot);
	
	return 0;
}

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243

四、实验结果

多叉树的先序遍历:
药品信息 双规制处方药 中成药 化学药品 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 单规制处方药 
多叉树的后序遍历:
中成药 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 化学药品 双规制处方药 单规制处方药 药品信息 
队列实现层序遍历:
药品信息 双规制处方药 单规制处方药 中成药 化学药品 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 
二叉树的层序遍历:
中成药 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 化学药品 双规制处方药 单规制处方药 药品信息 
1
2
3
4
5
6
7
8