短网址在线生成哪个好,网站seo链接购买,深圳大事件,收银系统目录 数据结构实验十 树遍历应用一、【实验目的】二、【实验内容】三、【实验源代码】⭐ CPP版⭐ c语言版 四、实验结果 数据结构实验十 树遍历应用
一、【实验目的】
1、了解树的建立方法 2、掌握树与二叉树的转化及其遍历的基本方法 3、掌握递归二叉树遍历算法的应用
二、… 目录 数据结构实验十 树遍历应用一、【实验目的】二、【实验内容】三、【实验源代码】⭐ CPP版⭐ c语言版 四、实验结果 数据结构实验十 树遍历应用
一、【实验目的】
1、了解树的建立方法 2、掌握树与二叉树的转化及其遍历的基本方法 3、掌握递归二叉树遍历算法的应用
二、【实验内容】
1.构造一棵药品信息树,树的形态如下图所示打印出先序遍历、后序遍历的遍历序列。 2.编写一个层序遍历算法利用队列结构按层次同一层自左至右输出树中所有的结点。 3.将树结构转化为二叉树编写二叉树非递归中序遍历算法并输出遍历序列。
三、【实验源代码】
⭐ CPP版
#include iostream
#include queue
#include stackusing namespace std;// 多叉树节点
struct Node {string name; // 节点名称vectorNode* nodes; // 子节点指针数组Node(string name, vectorNode* 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(其他用药, {});// 第三层vectorNode* ns1 {n31, n32, n33, n34, n35, n36};Node* n21 new Node(中成药, {});Node* n22 new Node(化学药品, ns1);// 第二层vectorNode* ns2 {n21, n22};Node* n11 new Node(双规制处方药, ns2);Node* n12 new Node(单规制处方药, {});// 第一层Node* root new Node(药品信息, {n11, n12}); // 根节点return root;
}// 队列实现层序遍历
void LevelOrderByQueue(Node* root) {queueNode* 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) {stackBinaryNode* 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; // 转换节点名称vectorNode* 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;
}
四、实验结果
多叉树的先序遍历:
药品信息 双规制处方药 中成药 化学药品 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 单规制处方药
多叉树的后序遍历:
中成药 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 化学药品 双规制处方药 单规制处方药 药品信息
队列实现层序遍历:
药品信息 双规制处方药 单规制处方药 中成药 化学药品 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药
二叉树的层序遍历:
中成药 神经系统用药 消化系统用药 呼吸系统用药 心脑血管系统用药 抗感染药 其他用药 化学药品 双规制处方药 单规制处方药 药品信息
