GDPU 数据结构 天码行空10

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

一、【实验目的】

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

二、【实验内容】

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

三、【实验源代码】

⭐ CPP版

#include <iostream>
#include <queue>
#include <stack>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;
}

⭐ c语言版

#include <stdio.h>
#include <stdlib.h>// 多叉树节点
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;
}

四、实验结果

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