当前位置： 首页 > news >正文

实验报告：实验4-树、二叉树与查找

news 2026/5/9 22:42:13

集美大学课程实验报告-实验4-树、二叉树与查找

项目名称 内容
课程名称 数据结构
班级 网安2512
学号 202521336040
实验项目名称 树、二叉树与查找
上机实践日期 2026.5.9
上机实践时间 2学时

一、目的（本次实验所涉及并要求掌握的知识点）

  • 掌握普通二叉树的链式存储结构，熟练实现先序创建、先序输出叶结点、递归求高度、层次遍历等基础操作，理解深度优先（DFS）与广度优先（BFS）遍历的差异。

  • 理解二叉排序树（BST）的定义与核心性质，掌握 BST 的创建、中序遍历、查找、插入等操作，验证 BST 中序遍历为升序序列的特性。

  • 了解哈希表与平衡树的设计思想，结合实际查询场景理解其适用场景，初步建立工程化问题的伪代码设计与实现思维。

  • 强化递归思维与问题拆解能力，掌握树形结构常见问题的分析方法，提升代码调试与复杂度分析能力，构建完整的树形数据结构知识体系。

二、实验内容与设计思想

题目1：先序序列创建二叉树。

函数相关伪代码

1. 定义二叉树节点：存储数据、左孩子、右孩子
2. 算法：先序创建二叉树输入字符串，下标从0开始读取字符，若为#则设为空节点，结束递归否则创建节点，递归创建左子树，再递归创建右子树
3. 算法：中序遍历二叉树若节点不为空，先遍历左子树，再输出数据，最后遍历右子树
4. 主程序循环读取输入的先序序列调用创建算法生成二叉树调用遍历算法输出结果

函数代码

#include <iostream>
#include <cstdlib>
#include <cstring>
//040cxy
using namespace std;// 二叉链表节点定义
typedef struct BiTNode {char data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;void CreateBiTree(BiTree &T, const char *str, int &index) {char ch = str[index++];if (ch == '#') { // # 表示空节点T = NULL;return;}// 创建当前节点T = (BiTree)malloc(sizeof(BiTNode));T->data = ch;// 递归创建左子树、右子树（前序顺序：根-左-右）CreateBiTree(T->lchild, str, index);CreateBiTree(T->rchild, str, index);
}void InOrderTraverse(BiTree T) {if (T) {InOrderTraverse(T->lchild);  // 先遍历左子树cout << T->data << " ";      // 访问根节点，输出+空格InOrderTraverse(T->rchild);  // 再遍历右子树}
}void DestroyBiTree(BiTree &T) {if (T) {DestroyBiTree(T->lchild);DestroyBiTree(T->rchild);free(T);T = NULL;}
}int main() {char str[101]; // 字符串长度不超过100// 多组测试数据，循环读取输入while (cin >> str) {BiTree T = NULL;int index = 0;// 1. 前序序列创建二叉树CreateBiTree(T, str, index);// 2. 中序遍历并输出InOrderTraverse(T);cout << endl; // 每组输出一行// 3. 释放内存DestroyBiTree(T);}return 0;
}

题目2：先序输出叶结点

函数相关伪代码

函数 PreorderPrintLeaves(BT):若 BT 为空，直接返回// 判断当前节点是否为叶子结点（左右孩子都为空）若 BT.Left 为空 且 BT.Right 为空:输出 " " + BT.Data  // 每个叶子前加一个空格// 先序遍历：先处理左子树，再处理右子树PreorderPrintLeaves(BT.Left)PreorderPrintLeaves(BT.Right)

函数代码

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;struct TNode {ElementType Data;BinTree Left;BinTree Right;
};// 题目要求实现的函数
void PreorderPrintLeaves(BinTree BT) {if (BT == NULL) return;if (BT->Left == NULL && BT->Right == NULL) {printf(" %c", BT->Data);}PreorderPrintLeaves(BT->Left);PreorderPrintLeaves(BT->Right);
}BinTree CreatBinTree() {BinTree T;char ch;// 修复scanf警告：接收返回值，同时去掉格式串里的空格if (scanf("%c", &ch) != 1) {return NULL;}if (ch == '#') {T = NULL;} else {T = (BinTree)malloc(sizeof(struct TNode));T->Data = ch;// 递归创建左右子树T->Left = CreatBinTree();T->Right = CreatBinTree();}return T;
}int main() {BinTree BT = CreatBinTree();printf("Leaf nodes are:");PreorderPrintLeaves(BT);printf("\n");return 0;
}

题目3：求二叉树高度

函数相关伪代码

函数 GetHeight(BT):// 空树的高度为0如果 BT 为空:返回 0// 递归计算左、右子树的高度左子树高度 = GetHeight(BT.Left)右子树高度 = GetHeight(BT.Right)// 二叉树高度 = 左右子树高度的最大值 + 1（当前节点的高度）返回 max(左子树高度, 右子树高度) + 1

函数代码

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;struct TNode {ElementType Data;BinTree Left;BinTree Right;
};int GetHeight(BinTree BT) {if (BT == NULL) {return 0;}int leftHeight = GetHeight(BT->Left);int rightHeight = GetHeight(BT->Right);return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}BinTree CreatBinTree() {// 创建节点BinTree A = (BinTree)malloc(sizeof(struct TNode)); A->Data = 'A';BinTree B = (BinTree)malloc(sizeof(struct TNode)); B->Data = 'B';BinTree C = (BinTree)malloc(sizeof(struct TNode)); C->Data = 'C';BinTree D = (BinTree)malloc(sizeof(struct TNode)); D->Data = 'D';BinTree F = (BinTree)malloc(sizeof(struct TNode)); F->Data = 'F';BinTree E = (BinTree)malloc(sizeof(struct TNode)); E->Data = 'E';BinTree G = (BinTree)malloc(sizeof(struct TNode)); G->Data = 'G';BinTree H = (BinTree)malloc(sizeof(struct TNode)); H->Data = 'H';BinTree I = (BinTree)malloc(sizeof(struct TNode)); I->Data = 'I';// 构建树结构A->Left = B; A->Right = C;B->Left = D; B->Right = F;F->Left = NULL; F->Right = E;C->Left = G; C->Right = I;G->Left = NULL; G->Right = H;// 叶子节点的左右孩子均为NULLD->Left = D->Right = NULL;E->Left = E->Right = NULL;H->Left = H->Right = NULL;I->Left = I->Right = NULL;return A;
}int main() {BinTree BT = CreatBinTree();printf("%d\n", GetHeight(BT)); return 0;
}

题目4：二叉树层次遍历(广度优先)

函数相关伪代码

// 1. 前序序列构建二叉树（跳过第一个#，#表示空节点）
函数 CreateTree(str, index):读取当前字符 ch = str[index]index = index + 1如果 ch 是 '#' 或 字符串结束:返回 空节点创建新节点，数据为 ch递归创建左子树：CreateTree(str, index)递归创建右子树：CreateTree(str, index)返回新节点// 2. 层次遍历（队列实现，控制输出格式）
函数 LevelOrder(root):如果根节点为空:输出 "NULL"，返回初始化队列，根节点入队设置 first 标记为 True（控制空格，第一个节点前无空格）当队列不为空:出队队首节点 node如果是第一个节点:输出 node.data，first = False否则:输出 " " + node.data如果 node 有左孩子，左孩子入队如果 node 有右孩子，右孩子入队

函数代码

#include <iostream>
#include <queue>
#include <string>
using namespace std;struct TreeNode {char data;TreeNode* left;TreeNode* right;TreeNode(char d) : data(d), left(NULL), right(NULL) {}
};string s;// 根据顺序存储构建二叉链表
TreeNode* buildTree(int index) {if (index >= s.length() || s[index] == '#')return NULL;TreeNode* node = new TreeNode(s[index]);node->left = buildTree(2 * index);node->right = buildTree(2 * index + 1);return node;
}// 层次遍历
void levelOrder(TreeNode* root) {if (!root) {cout << "NULL";return;}queue<TreeNode*> q;q.push(root);bool first = true;while (!q.empty()) {TreeNode* cur = q.front();q.pop();if (first) {cout << cur->data;first = false;} else {cout << " " << cur->data;}if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);}
}int main() {cin >> s;TreeNode* root = buildTree(1); levelOrder(root);return 0;
}

题目5：创建二叉排序树并对其进行中序遍历

函数相关伪代码

1. 定义二叉排序树节点：存储数值、左孩子、右孩子
2. 插入节点算法：若树空，新建节点作为根数值 < 根节点 → 插入左子树数值 > 根节点 → 插入右子树
3. 创建二叉排序树：循环读取输入数字，遇到 # 停止逐个将数字插入树中
4. 中序遍历：递归遍历左子树 → 输出根节点 → 递归遍历右子树

函数代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 二叉排序树节点结构
typedef struct BSTNode {int data;               // 节点值struct BSTNode *lchild; // 左孩子struct BSTNode *rchild; // 右孩子
} BSTNode, *BSTree;void InsertBST(BSTree &T, int val) {// 空树，创建新节点if (T == NULL) {T = (BSTree)malloc(sizeof(BSTNode));T->data = val;T->lchild = T->rchild = NULL;return;}// 小于根节点，插入左子树if (val < T->data) {InsertBST(T->lchild, val);}// 大于根节点，插入右子树else if (val > T->data) {InsertBST(T->rchild, val);}
}void InOrder(BSTree T, int &first) {if (T) {InOrder(T->lchild, first);if (first) {printf("%d", T->data);first = 0;} else {printf(" %d", T->data);}InOrder(T->rchild, first);}
}int main() {BSTree T = NULL; // 初始化空树char str[10];    // 接收输入（数字或#）int first = 1;   // 格式控制// 循环读取输入，遇到#停止while (scanf("%s", str) != EOF) {if (strcmp(str, "#") == 0) {break;}int val = atoi(str); // 字符串转整数InsertBST(T, val);   // 插入节点}// 中序遍历输出InOrder(T, first);printf("\n");return 0;
}

题目6：BST（二叉排序树）的查找、插入与建树与删除

函数相关伪代码

1. 定义BST节点：数据、左孩子、右孩子
2. 查找算法：若树空 → 查找失败目标值 = 根节点 → 查找成功目标值 < 根节点 → 递归查找左子树目标值 > 根节点 → 递归查找右子树
3. 插入算法：若树空 → 新建节点值 < 根 → 插入左子树值 > 根 → 插入右子树
4. 建树算法：初始化空树循环读取数字，遇到#停止逐个调用插入函数
5. 删除算法（分3种情况）：① 叶子节点：直接删除② 单孩子节点：用子节点替代③ 双孩子节点：找右子树最小值替代，再删除最小值
6. 中序遍历：左→根→右（输出升序序列）

函数代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 二叉排序树节点结构定义
typedef struct BSTNode {int data;               // 节点数据struct BSTNode *lchild; // 左子树struct BSTNode *rchild; // 右子树
} BSTNode, *BSTree;// ===================== 1. 查找操作 =====================
// 功能：查找值为key的节点，成功返回节点指针，失败返回NULL
BSTree SearchBST(BSTree T, int key) {if (T == NULL || T->data == key) {return T;}// 小于根节点，查找左子树if (key < T->data) {return SearchBST(T->lchild, key);}// 大于根节点，查找右子树else {return SearchBST(T->rchild, key);}
}// ===================== 2. 插入操作（纯C二级指针） =====================
// 功能：向BST中插入值val，重复值不插入
void InsertBST(BSTree *T, int val) {// 找到空位置，创建新节点if (*T == NULL) {*T = (BSTree)malloc(sizeof(BSTNode));(*T)->data = val;(*T)->lchild = (*T)->rchild = NULL;return;}// 重复值，不插入if (val == (*T)->data) {return;}// 插入左子树if (val < (*T)->data) {InsertBST(&(*T)->lchild, val);}// 插入右子树else {InsertBST(&(*T)->rchild, val);}
}// ===================== 3. 删除操作（核心，3种情况） =====================
// 功能：删除值为key的节点，返回新的根节点
BSTree DeleteBST(BSTree T, int key) {if (T == NULL) {printf("删除失败：节点不存在！\n");return NULL;}// 递归查找待删除节点if (key < T->data) {T->lchild = DeleteBST(T->lchild, key);} else if (key > T->data) {T->rchild = DeleteBST(T->rchild, key);}// 找到待删除节点else {BSTree p;// 情况1：叶子节点（无孩子）if (T->lchild == NULL && T->rchild == NULL) {free(T);return NULL;}// 情况2：只有右孩子else if (T->lchild == NULL) {p = T->rchild;free(T);return p;}// 情况3：只有左孩子else if (T->rchild == NULL) {p = T->lchild;free(T);return p;}// 情况4：左右孩子都存在 → 找右子树最小值替换p = T->rchild;while (p->lchild != NULL) {p = p->lchild;}// 替换数据T->data = p->data;// 删除替换节点T->rchild = DeleteBST(T->rchild, p->data);}return T;
}// ===================== 4. 中序遍历（升序，无末尾空格） =====================
void InOrderTraverse(BSTree T) {static int flag = 1; // 标记第一个元素，控制空格if (T != NULL) {InOrderTraverse(T->lchild);if (flag) {printf("%d", T->data);flag = 0;} else {printf(" %d", T->data);}InOrderTraverse(T->rchild);}
}// ===================== 5. 销毁二叉树（释放内存） =====================
void DestroyBST(BSTree *T) {if (*T != NULL) {DestroyBST(&(*T)->lchild);DestroyBST(&(*T)->rchild);free(*T);*T = NULL;}
}// ===================== 主函数：完整测试 =====================
int main() {BSTree T = NULL;char str[10];int num;// ========== 1. 建树 ==========printf("===== 构建二叉排序树 =====\n");printf("请输入节点序列(以 # 结束)：\n");while (scanf("%s", str) != EOF) {if (strcmp(str, "#") == 0) {break;}num = atoi(str);InsertBST(&T, num);}// ========== 2. 中序遍历 ==========printf("\n中序遍历结果(升序)：");InOrderTraverse(T);printf("\n");// ========== 3. 查找测试 ==========int key1 = 30;if (SearchBST(T, key1)) {printf("查找 %d：成功\n", key1);} else {printf("查找 %d：失败\n", key1);}// ========== 4. 删除测试（覆盖3种情况） ==========// 测试1：删除双孩子节点 30printf("\n===== 删除双孩子节点 30 =====\n");T = DeleteBST(T, 30);printf("删除后中序遍历：");InOrderTraverse(T);printf("\n");// 测试2：删除叶子节点 23printf("\n===== 删除叶子节点 23 =====\n");T = DeleteBST(T, 23);printf("删除后中序遍历：");InOrderTraverse(T);printf("\n");// 测试3：删除单孩子节点 25printf("\n===== 删除单孩子节点 25 =====\n");T = DeleteBST(T, 25);printf("删除后中序遍历：");InOrderTraverse(T);printf("\n");// 释放内存DestroyBST(&T);return 0;
}

题目7：航空公司VIP客户查询

函数相关伪代码

1. 定义哈希表节点结构：身份证号 id[20]累计里程 score下一个节点指针 next2. 定义哈希表 hashTable[HASH_SIZE]，初始化为空指针3. 哈希函数 hash(s):h = 0对每个字符 c in s:h = h * 131 + c  // 多项式哈希，降低冲突率返回 h % HASH_SIZE4. 插入函数 insert(id, addScore):idx = hash(id)遍历 hashTable[idx] 链表:若当前节点.id == id:当前节点.score += addScore返回新建节点，存入id和addScore，头插入链表5. 查询函数 query(id):idx = hash(id)遍历 hashTable[idx] 链表:若当前节点.id == id:返回 当前节点.score返回 -1（表示不存在）6. 主程序:读 N 和 K初始化哈希表循环 N 次:读 id 和 distanceadd = max(distance, K)  // 低于K按K计算insert(id, add)读 M循环 M 次:读 idres = query(id)res == -1 → 输出 No Info否则 → 输出 res

函数代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define HASH_SIZE 100003
#define ID_LEN 20// 哈希链表节点
typedef struct Node {char id[ID_LEN];int mile;struct Node *next;
} Node;// 全局哈希表（正确声明）
Node *hashTable[HASH_SIZE];// 稳定字符串哈希函数（兼容数字+X）
unsigned int getHash(const char *s) {unsigned int val = 0;int i = 0;while (s[i] != '\0') {val = val * 11 + s[i];i++;}return val % HASH_SIZE;
}// 插入/累加里程
void insert(const char *id, int add) {unsigned int idx = getHash(id);Node *p = hashTable[idx];// 查找已存在的用户while (p != NULL) {if (strcmp(p->id, id) == 0) {p->mile += add;return;}p = p->next;}// 新建节点Node *newNode = (Node *)malloc(sizeof(Node));strcpy(newNode->id, id);newNode->mile = add;newNode->next = hashTable[idx];hashTable[idx] = newNode;
}// 查询函数
int query(const char *id) {unsigned int idx = getHash(id);Node *p = hashTable[idx];while (p != NULL) {if (strcmp(p->id, id) == 0) {return p->mile;}p = p->next;}return -1;
}int main() {int N, K;scanf("%d %d", &N, &K);for (int i = 0; i < HASH_SIZE; i++) {hashTable[i] = NULL;}// 录入飞行记录for (int i = 0; i < N; i++) {char id[ID_LEN];int dis;scanf("%s %d", id, &dis);int add = (dis > K) ? dis : K;insert(id, add);}// 处理查询int M;scanf("%d", &M);for (int i = 0; i < M; i++) {char id[ID_LEN];scanf("%s", id);int res = query(id);if (res == -1) {printf("No Info\n");} else {printf("%d\n", res);}}return 0;
}

三、实验使用环境（本次实验所使用的平台和相关软件）

以下请根据实际情况编写

  • 操作系统：Windows 11专业版
  • 编程语言：C++
  • 开发工具：DEV C++
  • 编译器：GCC

四、实验步骤和调试过程（实验步骤、测试数据设计、测试结果分析）

题目1：先序序列创建二叉树

本机运行截图
image

PTA提交截图
image

题目2：先序输出叶结点

本机运行截图
image

PTA提交截图
image

题目3：求二叉树高度

本机运行截图
image

PTA提交截图
image

题目4：二叉树层次遍历(广度优先)

本机运行截图
image

PTA提交截图
image

题目5：创建二叉排序树并对其进行中序遍历

本机运行截图
image

题目6：BST（二叉排序树）的查找、插入与建树与删除

本机运行截图
image

题目7：区间删除（符号配对）

本机运行截图
image

PTA提交截图
image

五、实验小结（实验中遇到的问题及解决过程、实验体会和收获）

遇到的问题及解决方法：

  1. 问题：二叉排序树（BST）删除节点后树结构被破坏，中序遍历结果混乱
    • 解决方法：初始代码未完整处理删除节点的三种情况（叶子节点、单孩子节点、双孩子节点），尤其是双孩子节点删除后未正确替换为右子树最小值，导致树结构出错。后续修正了删除逻辑，对三种情况分别处理，双孩子节点采用 “右子树最小值替换 + 递归删除替换节点” 的方式，保证删除后树的有序性不受影响。
  2. 问题：程序运行时出现崩溃、野指针访问错误
    • 解决方法：在哈希表、BST 的实现中，多次出现空指针访问、野指针问题，如哈希表未初始化、BST 删除节点后未正确赋值空指针。通过 IDE 的断点调试功能，逐行检查指针状态，规范了内存分配与指针赋值操作，确保所有指针使用前都已初始化，避免了非法访问。

实验体会和收获：

  • 理解了数据结构设计的核心思想：哈希表的核心是解决冲突、保证查询效率，二叉排序树的核心是维持有序性，这些设计思想也为后续的学习提供了思路，认识到数据结构的选择需要结合实际场景的需求
  • 本次实验系统掌握了多种数据结构的实现与应用，包括二叉排序树的增删查改、链地址法哈希表的实现、二叉树的前序构建与层次遍历，理解了不同数据结构的适用场景：哈希表适合大规模数据的快速查询，二叉排序树适合有序数据的操作，二叉树的构建与遍历则是树形结构的基础，为后续更复杂的数据结构学习打下了基础。
  • 深刻认识到代码规范与输出格式的重要性，不仅学会了用 IDE 的格式化工具统一代码缩进，更理解了题目输出格式的严格性

六、附件（参考文献和相关资料）

  1. 实验4-树、二叉树与查找
http://www.jsqmd.com/news/785687/

相关文章：

  • 从儿童AI认知偏差看人工智能素养教育的核心转向
  • 各地特色糖水，正宗做法大公开
  • 周作业66
  • 洛谷P6054思路分享（网络流，期望）
  • DeepSeek V4 上线，Tabbit 更会干活了（限时白嫖 pro 会员）
  • Kubernetes自定义资源定义(CRD)深度解析与实践
  • CANN/mat-chem-sim-pred DPD算子设计文档
  • STM32 内核
  • 呼和浩特搬家怎么选？2025年本地搬家市场格局与五大机构深度测评 - 品牌策略师
  • CANN/AMCT保存量化重训练模型
  • CANN/cann-recipes-infer Kimi-K2-Thinking配置指南
  • JAVA TREE
  • cann/runtime 多设备编程
  • 卷积改进与轻量化：2026 生产级轻量：将 MobileOne 重新参数化块引入 YOLO 主干，iPhone 上实时运行
  • Kubernetes多集群管理与联邦：构建跨地域高可用架构
  • 异常类
  • 2026年4月技术好的升降窗品牌推荐，断桥窗沙一体内开窗/铝合金阳光房/系统推拉门/阳光房，升降窗厂家哪个好 - 品牌推荐师
  • 基于OpenAI API与Slack平台构建智能对话机器人的实践指南
  • Avast 阻止引用程序访问网络
  • 生产级AI系统不确定性管理：从量化到决策的工程实践
  • CANN竞赛仓Add算子测试报告
  • 在Windows 11上无缝运行Android应用：Windows Subsystem for Android完整指南
  • 2026年好用的免费在线去水印工具怎么选？免费一键去水印网站最新推荐 - 科技热点发布
  • 一键部署AI助手沙箱：OpenClaw计算机容器在ModelScope与HuggingFace的实战指南
  • 基于NGSI-LD的物联网数据质量评估与增强实践
  • EDA-设计规模爆炸
  • LeetCode 3629.通过质数传送到达终点的最少跳跃次数：埃式筛+BFS
  • 有没有哪家包间又带独立厕所环境又好
  • 文献计量分析揭示AI在金融与创业交叉领域的研究热点与趋势
  • 我的编程启程：从零基础出发，奔赴心之所向