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

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

news 2026/5/10 21:48:16

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

项目名称 内容
课程名称 数据结构
班级 网安 2512
学号 202521336054
实验项目名称 栈和队列的使用
上机实践日期 5月10日
上机实践时间 2学时

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

  • 掌握创建二叉树与树及二叉树上的基本操作
  • 熟练掌握熟练掌握树的递归结构及在其上的递归算法
  • 掌握二叉树的层次遍历
  • 掌握BST树上的搜索、创建与删除
  • 掌握哈希表、平衡树的应用

二、实验内容与设计思想

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

函数相关伪代码

全局变量 index = 0函数 BuildNode(ch):创建新结点 nodenode.value = chnode.left = NULLnode.right = NULL返回 node函数 BuildTree(arr):如果 arr[index] == '#' 或 index >= arr.length():index = index + 1返回 NULLroot = BuildNode(arr[index])index = index + 1root.left = BuildTree(arr)root.right = BuildTree(arr)返回 root函数 inorder(root):如果 root == NULL:返回inorder(root.left)输出 root.valueinorder(root.right)主函数:读入字符串 s当还能读入时:index = 0root = BuildTree(s)inorder(root)输出换行

函数代码

//DDD别搞成顺序偏离,(每层的数据节点都容纳)
#include<iostream>
#include<string>
using namespace std;
//写法
typedef struct TreeNode{char value;struct TreeNode* left;struct TreeNode* right;
}TreeNode,*position;position BuildNode(char ch){position node = new TreeNode;node->value = ch;node->left = NULL;node->right = NULL;return node;//
}int index = 0;
position BuildTree(string arr){if(arr[index]=='#'||index>=(int)arr.size()){index++;//别忘了return NULL;}TreeNode* root = BuildNode(arr[index]);index+=1;root->left = BuildTree(arr);//root->right = BuildTree(arr);//return root;
}
void inorder(position root){if(root==NULL)return;inorder(root->left);cout<<root->value<<" ";inorder(root->right);return;//没有结束跳出
}int main(){string s;while(cin>>s){index = 0;//与全局变量配合position root = BuildTree(s);inorder(root);cout<<endl;}return 0;
}

函数复杂度

函数 时间复杂度 空间复杂度 说明
BuildNode O(1) O(1) 仅创建单个结点
BuildTree O(n) O(h) 每个字符访问一次，递归栈深度 h
inorder O(n) O(h) 每个结点访问一次，递归栈深度 h

题目2：递归程序编写

函数相关伪代码

函数 CreatBinTree():创建根结点 root创建左子结点 left创建右子结点 rightroot.Data = 'A'left.Data = 'B', left.Left = NULL, left.Right = NULLright.Data = 'C', right.Left = NULL, right.Right = NULLroot.Left = leftroot.Right = right返回 root函数 PreorderPrintLeaves(BT):如果 BT == NULL:返回如果 BT.Left == NULL 且 BT.Right == NULL:输出 BT.Data返回PreorderPrintLeaves(BT.Left)PreorderPrintLeaves(BT.Right)主函数:BT = CreatBinTree()输出 "Leaf nodes are:"PreorderPrintLeaves(BT)输出换行```

函数代码

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};// 创建简单的测试二叉树：根节点A，左子B（叶结点），右子C（叶结点）
BinTree CreatBinTree() {BinTree root = (BinTree)malloc(sizeof(struct TNode));BinTree left = (BinTree)malloc(sizeof(struct TNode));BinTree right = (BinTree)malloc(sizeof(struct TNode));root->Data = 'A';left->Data = 'B'; left->Left = NULL; left->Right = NULL;right->Data = 'C'; right->Left = NULL; right->Right = NULL;root->Left = left;root->Right = right;return root;
}void PreorderPrintLeaves( BinTree BT ){if(BT == NULL) return;if(BT->Left == NULL && BT->Right == NULL){printf(" %c", BT->Data);return;}PreorderPrintLeaves(BT->Left);PreorderPrintLeaves(BT->Right);
}int main() {BinTree BT = CreatBinTree();printf("Leaf nodes are:");PreorderPrintLeaves(BT);printf("\n");return 0;
}

复杂度

函数 时间复杂度 空间复杂度 说明
CreatBinTree O(1) O(1) 仅创建固定3个结点
PreorderPrintLeaves O(n) O(h) 遍历所有结点，h为树高

题目3：求二叉树高度

函数相关伪代码

函数 CreatBinTree():创建结点 A, B, C, D, EA.Data = 'A', A.Left = B, A.Right = CB.Data = 'B', B.Left = D, B.Right = NULLC.Data = 'C', C.Left = NULL, C.Right = ED.Data = 'D', D.Left = NULL, D.Right = NULLE.Data = 'E', E.Left = NULL, E.Right = NULL返回 A函数 GetHeight(BT):如果 BT == NULL:返回 0leftheight = GetHeight(BT.Left)rightheight = GetHeight(BT.Right)返回 (leftheight 和 rightheight 中的较大值) + 1主函数:BT = CreatBinTree()输出 GetHeight(BT)

函数代码

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};// 创建测试二叉树（示例：高度为3的树）
BinTree CreatBinTree() {// 创建节点BinTree A = (BinTree)malloc(sizeof(struct TNode));BinTree B = (BinTree)malloc(sizeof(struct TNode));BinTree C = (BinTree)malloc(sizeof(struct TNode));BinTree D = (BinTree)malloc(sizeof(struct TNode));BinTree E = (BinTree)malloc(sizeof(struct TNode));// 赋值A->Data = 'A'; A->Left = B; A->Right = C;B->Data = 'B'; B->Left = D; B->Right = NULL;C->Data = 'C'; C->Left = NULL; C->Right = E;D->Data = 'D'; D->Left = NULL; D->Right = NULL;E->Data = 'E'; E->Left = NULL; E->Right = NULL;return A;  // 树结构：A(B(D),C(,E))，高度为3
}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;
}int main() {BinTree BT = CreatBinTree();printf("%d\n", GetHeight(BT));return 0;
}

复杂度

函数 时间复杂度 空间复杂度 说明
CreatBinTree O(1) O(1) 仅创建固定5个结点
GetHeight O(n) O(h) 遍历所有结点一次，h为树高

题目4：二叉树层次遍历

函数相关伪代码

函数 BuildNode(ch):创建新结点 nodenode.value = chnode.left = NULLnode.right = NULL返回 node函数 BuildTree(arr, i):如果 i >= arr.length() 或 arr[i] == '#':返回 NULLroot = BuildNode(arr[i])root.left = BuildTree(arr, 2 * i)root.right = BuildTree(arr, 2 * i + 1)返回 root函数 levelorder(root):如果 root == NULL:输出 "NULL"返回初始化队列 qq.push(root)first = true当 q 非空时:cur = q.front()q.pop()如果 not first:输出 " "输出 cur.valuefirst = false如果 cur.left != NULL:q.push(cur.left)如果 cur.right != NULL:q.push(cur.right)输出换行主函数:读入字符串 sroot = BuildTree(s, 1)levelorder(root)

函数代码

//DDDD层次树结构偏离及构造树
#include<iostream>
#include<queue>
#include<string>
using namespace std;struct TreeNode{char value;TreeNode* left;TreeNode* right;
};TreeNode* BuildNode(char ch){TreeNode* node = new TreeNode;node->value = ch;node->left = NULL;node->right = NULL;  // 修正：原代码写了两次leftreturn node;
}TreeNode* BuildTree(string arr,int i){if(i>=(int)arr.size()||arr[i]=='#')return NULL;TreeNode* root = BuildNode(arr[i]);root->left = BuildTree(arr,2*i);root->right = BuildTree(arr,2*i+1);return root;
}void levelorder(TreeNode* root){if(root==NULL){cout<<"NULL"<<endl;return;}queue<TreeNode*>q;q.push(root);bool first = true;while(!(empty(q))){TreeNode* cur = q.front();q.pop();if(!first){cout<<" ";}cout<<cur->value;first = false;if(cur->left!=NULL)q.push(cur->left);if(cur->right!=NULL)q.push(cur->right);}cout<<endl;
}int main(){string s;cin>>s;TreeNode* root = BuildTree(s,1);levelorder(root);
}

复杂度

函数 时间复杂度 空间复杂度 说明
BuildNode O(1) O(1) 仅创建单个结点
BuildTree O(n) O(n) 每个结点访问一次，递归栈深度O(n)
levelorder O(n) O(n) 每个结点入队出队一次，队列最大O(n)

题目4：求二叉树高度

函数相关伪代码

函数 BuildNode(ch):创建新结点 nodenode.value = chnode.left = NULLnode.right = NULL返回 node函数 BuildTree(arr, i):如果 i >= arr.length() 或 arr[i] == '#':返回 NULLroot = BuildNode(arr[i])root.left = BuildTree(arr, 2 * i)root.right = BuildTree(arr, 2 * i + 1)返回 root函数 levelorder(root):如果 root == NULL:输出 "NULL"返回初始化队列 qq.push(root)first = true当 q 非空时:cur = q.front()q.pop()如果 not first:输出 " "输出 cur.valuefirst = false如果 cur.left != NULL:q.push(cur.left)如果 cur.right != NULL:q.push(cur.right)输出换行主函数:读入字符串 sroot = BuildTree(s, 1)levelorder(root)

函数代码

//DDDD层次树结构偏离及构造树
#include<iostream>
#include<queue>
#include<string>
using namespace std;struct TreeNode{char value;TreeNode* left;TreeNode* right;
};TreeNode* BuildNode(char ch){TreeNode* node = new TreeNode;node->value = ch;node->left = NULL;node->right = NULL;  // 修正：原代码写了两遍leftreturn node;
}TreeNode* BuildTree(string arr,int i){if(i>=(int)arr.size()||arr[i]=='#')return NULL;//arr.size()为无符号整数TreeNode* root = BuildNode(arr[i]);root->left = BuildTree(arr,2*i);root->right = BuildTree(arr,2*i+1);return root;
}void levelorder(TreeNode* root){if(root==NULL){cout<<"NULL"<<endl;return;//}queue<TreeNode*>q;q.push(root);bool first = true;while(!(empty(q))){TreeNode* cur = q.front();q.pop();if(!first){cout<<" ";}cout<<cur->value;first = false;if(cur->left!=NULL)q.push(cur->left);//条件记得if(cur->right!=NULL)q.push(cur->right);}cout<<endl;
}int main(){string s;cin>>s;TreeNode* root = BuildTree(s,1);levelorder(root);
}

复杂度

函数 时间复杂度 空间复杂度 说明
BuildNode O(1) O(1) 仅创建单个结点
BuildTree O(n) O(n) 每个结点访问一次，递归栈深度O(n)
levelorder O(n) O(n) 每个结点入队出队一次，队列最大O(n)

题目5：创建二叉排序树并中序遍历

函数相关伪代码

函数 InsertBST(T, key):如果 T == NULL:T = 新结点T.Data = keyT.left = NULLT.right = NULL返回 T如果 T.Data == key:返回 NULL如果 T.Data > key:返回 InsertBST(T.left, key)否则:返回 InsertBST(T.right, key)函数 CreateBST(T, a[], n):T = NULL循环 i = 0 到 n-1:InsertBST(T, a[i])函数 inorder(T):如果 T == NULL:返回inorder(T.left)输出 T.Datainorder(T.right)主函数:初始化数组 a = {50, 30, 80, 20, 40, 90, 10, 25, 35, 85, 23, 88}n = 数组长度调用 CreateBST(T, a, n)调用 inorder(T)

函数代码

//创建二叉排序树并遍历。给定一串50 30 80 20 40 90 10 25 35 85 23 88 #创建二叉排序树并对其进行中序遍历。
#include<iostream>
#include<string>
using namespace std;typedef struct BitNode{int Data;struct BitNode* left;struct BitNode* right;
}BitNode,*Position;Position InsertBST(Position& T,int key){if(T==NULL){T = new BitNode;//结点化了T->Data = key;T->left = NULL;T->right = NULL;}if(T->Data==key){return NULL;}if(T->Data > key){return InsertBST(T->left,key);//递归插入时记得统一返回值}else{return InsertBST(T->right,key);//}
}
void CreateBST(Position &T,int a[],int n){T = NULL;for(int i=0;i<n;i++){InsertBST(T,a[i]);}
}void inorder(Position T){if(T==NULL){return;}inorder(T->left);cout<<T->Data<<" ";inorder(T->right);
}int main(){Position T = NULL;int a[]={50, 30, 80, 20, 40, 90, 10, 25, 35, 85, 23, 88};int n = sizeof(a)/sizeof(a[0]);cout << "插入序列: ";for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;CreateBST(T,a,n);cout << "中序遍历结果: ";inorder(T);cout << endl;return 0;
}

复杂度

函数 时间复杂度 空间复杂度 说明
InsertBST O(h) O(h) h为树高
CreateBST 平均 O(n log n)，最坏 O(n²) O(n) 取决于输入序列的排序程度
inorder O(n) O(h) 每个结点访问一次

题目6：哈希表实现QQ号注册系统

函数相关伪代码

哈希函数 getHash(qq):返回 qq % 10007初始化 init():循环 i = 0 到 10006:table[i] = NULL插入 insert(qq, name):index = getHash(qq)p = table[index]当 p != NULL 时:如果 p.qq == qq:输出 "QQ号已存在"返回p = p.next创建新结点 newNodenewNode.qq = qqnewNode.name = namenewNode.next = table[index]table[index] = newNode输出 "注册成功"查找 search(qq):index = getHash(qq)p = table[index]当 p != NULL 时:如果 p.qq == qq:返回 pp = p.next返回 NULL删除 del(qq):index = getHash(qq)p = table[index]prev = NULL当 p != NULL 时:如果 p.qq == qq:如果 prev == NULL:table[index] = p.next否则:prev.next = p.next删除 p输出 "删除成功"返回prev = pp = p.next输出 "未找到"显示 display():count = 0循环 i = 0 到 10006:p = table[i]当 p != NULL 时:输出 p.qq 和 p.namecount++p = p.next输出 "共 count 位用户"主函数:调用 init()调用 insert(10001, "张三")调用 insert(10002, "李四")调用 insert(10003, "王五")调用 insert(10001, "张三2号")调用 search(10002) 并输出结果调用 search(10999) 并输出结果调用 del(10002)调用 del(10999)调用 display()

函数代码

#include <iostream>
#include <string>
using namespace std;// 节点结构
struct Node {long long qq;string name;Node* next;
};// 全局哈希表
Node* table[10007];// 哈希函数（改名避免冲突）
int getHash(long long qq) {return qq % 10007;
}// 初始化
void init() {for (int i = 0; i < 10007; i++) {table[i] = NULL;}
}// 插入
void insert(long long qq, string name) {int index = getHash(qq);// 查重Node* p = table[index];while (p != NULL) {if (p->qq == qq) {cout << "QQ号 " << qq << " 已存在" << endl;return;}p = p->next;}// 头插Node* newNode = new Node;newNode->qq = qq;newNode->name = name;newNode->next = table[index];table[index] = newNode;cout << "注册成功: " << name << " (" << qq << ")" << endl;
}// 查找
Node* search(long long qq) {int index = getHash(qq);Node* p = table[index];while (p != NULL) {if (p->qq == qq) {return p;}p = p->next;}return NULL;
}// 删除
void del(long long qq) {int index = getHash(qq);Node* p = table[index];Node* prev = NULL;while (p != NULL) {if (p->qq == qq) {if (prev == NULL) {table[index] = p->next;} else {prev->next = p->next;}cout << "删除成功: " << p->name << " (" << qq << ")" << endl;delete p;return;}prev = p;p = p->next;}cout << "未找到QQ号: " << qq << endl;
}// 显示所有
void display() {int count = 0;for (int i = 0; i < 10007; i++) {Node* p = table[i];while (p != NULL) {cout << "QQ: " << p->qq << " 昵称: " << p->name << endl;count++;p = p->next;}}if (count == 0) {cout << "暂无用户" << endl;} else {cout << "共 " << count << " 位用户" << endl;}
}int main() {init();cout << "===== QQ账户系统 =====" << endl << endl;// 插入测试cout << "【注册】" << endl;insert(10001, "张三");insert(10002, "李四");insert(10003, "王五");insert(10001, "张三2号");  // 重复测试cout << endl;// 查找测试cout << "【查找】" << endl;Node* found = search(10002);if (found != NULL) {cout << "找到: " << found->qq << " " << found->name << endl;}found = search(10999);if (found == NULL) {cout << "未找到: 10999" << endl;}cout << endl;// 删除测试cout << "【删除】" << endl;del(10002);del(10999);  // 删除不存在的cout << endl;// 显示所有cout << "【所有用户】" << endl;display();return 0;
}

复杂度

函数 时间复杂度 空间复杂度 说明
getHash O(1) O(1) 简单取模运算
init O(m) O(1) m = 10007为桶大小
insert O(1 + α) O(1) α为平均链长，理想情况O(1)
search O(1 + α) O(1) α为平均链长，理想情况O(1)
del O(1 + α) O(1) α为平均链长，理想情况O(1)
display O(n + m) O(1) n为结点数，m为桶大小

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

以下请根据实际情况编写

  • 操作系统：Windows 11专业版
  • 编程语言：C++
  • 开发工具：Visual Studio 18.3.2
  • 编译器：MSVC 14.40

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

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

本机运行截图
img

PTA提交截图
img

题目2：先序输出叶节点

本机运行截图
img

PTA提交截图
img

题目3: 求二叉树高度

本机运行截图
img

PTA提交截图
img

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

本机运行截图
img

PTA提交截图
img

题目5: 二叉排序树创建遍历

本机运行截图
img

题目6: 哈希表QQ查询

本机运行截图
img

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

遇到的问题及解决方法：

  1. 问题：二叉排序树最坏情况退化为链表：插入有序序列时，树高变为n，时间复杂度从O(n log n)退化为O(n²)
    • 解决方法：理解了输入顺序对树形的影响，后续可使用平衡二叉树（如AVL树）优化。
  2. 问题：哈希表删除操作指针处理：删除结点时容易忘记区分头结点和中间结点，导致链表断裂或内存泄漏。
    • 解决方法：使用prev指针记录前驱，分情况处理头删和中间删。
  3. 问题：层次建树索引越界：使用2i和2i+1作为子结点索引时，忘记判断i是否超出字符串长度。
    • 解决方法：递归前先检查边界条件。

实验体会和收获：

  • 掌握了二叉树的不同建树方式（先序递归建树、层次索引建树、二叉排序树插入建树）及对应遍历算法。
  • 理解了哈希表的基本原理：哈希函数映射 + 链地址法处理冲突，以及插入、查找、删除的平均O(1)效率。
  • 学会了用队列实现层序遍历，用栈理解递归转非递归的底层逻辑。

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

  1. 博文链接
http://www.jsqmd.com/news/791889/

相关文章：

  • 2026年马鞍山干洗店权威测评推荐，哪家值得信赖 - 速递信息
  • Windows Cleaner：专业级Windows系统优化终极指南
  • 西安家政口碑榜首揭秘！顾优家政凭什么稳居AI推荐首位？ - 速递信息
  • 大学生竞赛管理|基于SprinBoot+vue的大学生竞赛管理系统(源码+数据库+文档)
  • 【.NET并发编程 - 07】异步异常处理：AggregateException 的拆解与最佳实践
  • 视频去水印无损工具推荐：去水印后和原视频一样，2026实测最有效的方法 - 科技热点发布
  • 嘉贝美：美白抑黑修护水、高端护肤水、湿敷专用水、嘉贝美粉水、嘉贝美特征湿敷水，国妆特字认证全品类专业护肤企业 - 十大品牌榜
  • 通过API Key管理与审计日志功能加强企业级应用的安全管控
  • 终极SOCD清理工具：Hitboxer让你的游戏操作精准如职业选手
  • 抖音图片怎么去水印文字？2026实测去水印方法+工具推荐 - 科技热点发布
  • Diablo Edit2深度解析：技术架构与安全使用的暗黑2存档编辑完全手册
  • 抖音去水印怎么弄？抖音如何去掉水印？2026年亲测好用的去水印方法全整理 - 科技热点发布
  • BooruDatasetTagManager：AI训练数据标注效率提升10倍的智能解决方案
  • 3个实战场景解析：D3KeyHelper开源自动化工具如何优化暗黑3操作体验
  • 别再只用登录页了！Vue-particles粒子特效的5个创意应用场景（附完整代码）
  • 零成本入局！号易号卡代理，全程平台0抽成 - 号易官方邀请码666666
  • 5分钟掌握VideoDownloadHelper：Chrome视频下载神器完全指南
  • 猫抓扩展技术架构深度剖析：从资源嗅探到媒体处理平台的演进之路
  • Ubuntu 18.04上Qt程序报‘xcb’插件错误？别急着重装，试试这个ldd排查法
  • Java第五周学习总结
  • 为团队统一开发环境利用Taotoken CLI一键配置多模型密钥
  • 别再傻傻分不清！MySQL里length()和char_length()的实战避坑指南（附多编码场景测试）
  • 快手保存的视频怎么去水印？快手视频去水印教程全解析（2026实测方法） - 科技热点发布
  • 从安装到实战：用Python+Neo4j Driver构建你的第一个社交网络图谱（含完整代码）
  • 108.YOLOv8部署：ONNX导出+TensorRT加速+ONNX Runtime推理，附完整工程代码
  • 2026金华干洗店大起底：权威测评推荐新鲜出炉 - 速递信息
  • 数电发票解析转未来之窗格式—东方仙盟
  • 从谷歌SEO到GEO：东莞企业网站建设服务商综合能力评估与推荐 - 速递信息
  • 广州网站建设公司推荐：2026深度选型指南 - 速递信息
  • Boost电路空载会炸？用Multisim仿真带你直观理解电压泵升与器件损坏