（大家好，今天分享的是数据结构的相关知识，大家可以在评论区进行互动答疑哦~加油！💕）
目录
提要：实验题目
一、实验目的
二、实验内容及要求
三、算法思想
实验1
实验2
四、源程序及注释
实验1代码（二叉树基本操作）
实验2代码（哈夫曼编码译码）
五、实验结果
实验1结果
实验2结果
提要：实验题目
1. 二叉树的遍历及基本操作
2. 二叉树中哈夫曼编码译码
一、实验目的
1.深入理解二叉树的基本概念和递归程序设计方法。
2.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序、中序、后序递归遍历，了解先序、中序和后序非递归遍历及层序遍历。
3.用二叉树解决实际问题，如掌握构造哈夫曼树及其编码和译码的方法。
二、实验内容及要求
1.建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果；
2.建立一棵二叉树，求二叉数的树的深度、统计叶子结点的个数、统计总的结点个数、进行层序遍历、交换左右子树等；
3.哈夫曼编码译码系统。
注：前两个题目必做，第3题选做。
三、算法思想
实验1
本实验的主要目的是实现二叉树的基本操作，包括创建二叉树、遍历（先序、中序、后序）、统计叶子节点的个数以及计算二叉树的深度。通过这些操作，我们可以理解二叉树的结构和基本特性。
1.二叉树的定义：二叉树是一种树形结构，每个节点最多有两个子节点（左子节点和右子节点）。在本实验中，二叉树的节点由 BiNode 结构体表示，包含节点数据、左孩子、右孩子和父节点指针。
2.树的创建：通过递归的方法构建二叉树。在输入时，用 # 表示空节点。每次输入一个节点后，递归调用创建其左子树和右子树。
3.树的遍历：
先序遍历：访问当前节点，然后递归访问左子树和右子树。
中序遍历：递归访问左子树，然后访问当前节点，最后递归访问右子树。
后序遍历：递归访问左子树和右子树后，再访问当前节点。
4.统计叶子节点：叶子节点是没有子节点的节点。通过递归的方法统计叶子节点的个数。
5.计算树的深度：树的深度是从根节点到最深叶子节点的最长路径。通过递归比较左子树和右子树的深度，返回较大的深度加一。
实验2
本实验的目标是实现哈夫曼编码和译码的基本功能。哈夫曼编码是一种无损数据压缩算法，通过构建哈夫曼树来为频率高的字符分配较短的编码，为频率低的字符分配较长的编码，从而有效减少编码后的数据大小。
1.哈夫曼树的定义：哈夫曼树是一种特殊的二叉树，用于生成可变长度的哈夫曼编码。每个叶子节点代表一个字符及其出现频率，树的结构使得字符的编码长度与其频率成反比。
2.优先队列：为了构建哈夫曼树，使用最小堆（优先队列）来存储节点。在每一步，取出频率最小的两个节点，合并成一个新的父节点，并将新节点插入优先队列。这个过程持续到队列中只剩一个节点，即哈夫曼树的根节点。
3.编码生成：遍历哈夫曼树，利用深度优先搜索（DFS）生成每个字符的哈夫曼编码。左子树分配编码‘0’，右子树分配编码‘1’。
4.译码过程：根据哈夫曼树和编码字符串，逐位解析编码。每遇到‘0’则转向左子节点，遇到‘1’则转向右子节点，直到达到叶子节点，提取相应的字符。
四、源程序及注释
实验1代码（二叉树基本操作）
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <stdbool.h>using namespace std;
//预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int status; //Status 是函数返回值类型，其值是函数结果状态代码
typedef char TElemType;//表示部分：
//创建结构体
typedef struct BiNode {TElemType data;struct BiNode* lchild; // 左孩子struct BiNode* rchild; // 右孩子struct BiNode* parent; // 父母
} BiNode, *BiTree;status Print(TElemType e) {cout << e << " ";return OK;
}//1. 创建二叉树
void CreateBiTree(BiTree &T) {TElemType a;cin >> a;if (a == '#') {T = NULL;} else {T = (BiNode*)malloc(sizeof(BiNode));if (!T) exit(OVERFLOW); T->data = a;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}//2. 先序遍历输出
void PreOrderTraverse(BiTree T, status (*Print)(TElemType e)) {if (T) {Print(T->data);PreOrderTraverse(T->lchild, Print);PreOrderTraverse(T->rchild, Print);}
}//3. 中序遍历输出
void InOrder(BiTree T, status(*Print)(TElemType e)) {if (T) {InOrder(T->lchild, Print);Print(T->data);InOrder(T->rchild, Print);}
}
//4. 后序遍历输出
void PostOrder(BiTree T, status(*Print)(TElemType e)) {if (T) {PostOrder(T->lchild, Print);PostOrder(T->rchild, Print);Print(T->data);}
}//5. 叶子结点的个数
void countleaf(BiTree T, int &num) {if (T) {if (!T->lchild && !T->rchild) num++;countleaf(T->lchild, num);countleaf(T->rchild, num);}
}//6. 二叉树的深度
int Depth(BiTree T) {if (!T) return 0; //树不为空int left = Depth(T->lchild);int right = Depth(T->rchild);return 1 + (left > right ? left : right);
}void showMenu() {cout << "********************************\n";cout << "**** 1. 创建二叉树 ****\n";cout << "**** 2. 先序遍历输出 ****\n";cout << "**** 3. 中序遍历输出 ****\n";cout << "**** 4. 后序遍历输出 ****\n";cout << "**** 5. 叶子结点的个数 ****\n";cout << "**** 6. 二叉树的深度 ****\n";cout << "**** 0. 退出程序 ****\n";cout << "********************************\n";
}int main() {BiTree T = NULL; //非空int i;int choose= -1;showMenu();while (choose != 0) {cout << "Please select（0-6）:";cin >> choose;switch (choose) {case 1://创建二叉树cout << "请输入树的结点（使用'#'表示空节点）：";CreateBiTree(T);break;case 2://先序遍历输出cout << "先序遍历输出为：";PreOrderTraverse(T, Print);cout << endl;break;case 3://中序遍历输出cout << "中序遍历输出为：";InOrder(T, Print);cout << endl;break;case 4://后序遍历输出cout << "后序遍历输出为：";PostOrder(T, Print);cout << endl;break;case 5: //叶子结点的个数{int num = 0; countleaf(T, num);cout << "叶子结点的个数为：" << num << endl;break;}case 6://二叉树的深度cout << "该二叉树的深度为：" << Depth(T) << endl;break;case 7://退出程序cout << "退出程序。" << endl; exit(0);break;default:cout << "无效输入，请重新输入！" << endl;break;}}
}实验2代码（哈夫曼编码译码）
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;//预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int status; // Status 是函数返回值类型
typedef char TElemType;// 哈夫曼树节点结构
struct BiNode {TElemType data;int freq;struct BiNode* left; // 左孩子struct BiNode* right; // 右孩子// 用于构建优先队列bool operator<(const BiNode& other) const {return freq > other.freq; // 最小堆}
};typedef BiNode* BiTree;// 用于构建哈夫曼树
BiTree CreateHuffmanTree(const vector<pair<TElemType, int>>& freqTable) {priority_queue<BiTree> pq;// 将字符和频率插入优先队列for (const auto& item : freqTable) {BiTree node = new BiNode{item.first, item.second, nullptr, nullptr};pq.push(node);}// 构建哈夫曼树while (pq.size() > 1) {BiTree left = pq.top(); pq.pop();BiTree right = pq.top(); pq.pop();BiTree parent = new BiNode{'\0', left->freq + right->freq, left, right};pq.push(parent);}return pq.top(); // 返回根节点
}// 生成哈夫曼编码
void GenerateCodes(BiTree root, const string& code, unordered_map<TElemType, string>& huffmanCodes) {if (root->left == nullptr && root->right == nullptr) {huffmanCodes[root->data] = code; // 叶子节点return;}if (root->left) GenerateCodes(root->left, code + '0', huffmanCodes);if (root->right) GenerateCodes(root->right, code + '1', huffmanCodes);
}// 译码
string DecodeHuffman(BiTree root, const string& encodedStr) {string decodedStr;BiTree currentNode = root;for (char bit : encodedStr) {currentNode = (bit == '0') ? currentNode->left : currentNode->right;// 到达叶子节点if (currentNode->left == nullptr && currentNode->right == nullptr) {decodedStr += currentNode->data; // 添加字符currentNode = root; // 重置到根节点}}return decodedStr;
}void showMenu() {cout << "********************************\n";cout << "**** 1. 构建哈夫曼树 ****\n";cout << "**** 2. 打印哈夫曼编码 ****\n";cout << "**** 3. 译码哈夫曼编码 ****\n";cout << "**** 0. 退出程序 ****\n";cout << "********************************\n";
}int main() {BiTree huffmanRoot = nullptr;unordered_map<TElemType, string> huffmanCodes;int choose= -1;showMenu();while (choose != 0) {cout << "Please select（0-3）:";cin >> choose;switch (choose) {case 1: {// 输入字符及其频率int n;cout << "请输入字符个数：";cin >> n;vector<pair<TElemType, int>> freqTable(n);cout << "请输入字符及其频率（字符 空格 频率）：\n";for (int i = 0; i < n; i++) {cin >> freqTable[i].first >> freqTable[i].second;}huffmanRoot = CreateHuffmanTree(freqTable);GenerateCodes(huffmanRoot, "", huffmanCodes);cout << "哈夫曼树构建完成！\n";break;}case 2: {cout << "哈夫曼编码：\n";for (const auto& pair : huffmanCodes) {cout << pair.first << ": " << pair.second << endl;}break;}case 3: {cout << "请输入要译码的哈夫曼编码：";string encodedStr;cin >> encodedStr;string decodedStr = DecodeHuffman(huffmanRoot, encodedStr);cout << "译码结果为：" << decodedStr << endl;break;}case 0:cout << "退出程序。" << endl;exit(0);default:cout << "无效输入，请重新输入！" << endl;break;}}return 0;
}五、实验结果
实验1结果
实验2结果
（今日分享暂时到此为止啦！为不断努力的自己鼓鼓掌吧🥳。今日文案分享：得胜当以你为期，越山先悦己。）