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

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

news 2026/5/13 14:57:05

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

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

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

掌握树、二叉树以及基于hash的查找等基础操作。
学习树和散列表的创建和修改操作。
理解树和散列表在实际问题中的应用。

二、实验内容与设计思想

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

主要函数伪代码

二叉树结构体BiTNode
//创建新节点BiTNode* MakeNode(char data)
//创建二叉树 
void MakeTree(BiTNode & root)
{输入xroot=MakeNode(x)  MakeTree(root->lchild)MakeTree(root->rchild)
}
//中序遍历二叉树
void inOrder(BiTree root)
{root==NULL return //先访问左子树inOrder(root->lchild)//再访问右子树inOrder(root->right)
}
//销毁二叉树
void DestroyTree(BiTNode*& root)
{//左右孩子置空，删除根节点并置空，为多次输入释放空间DestroyTree(root->lchild)DestroyTree(root->rchild)delete rootroot = NULL;
}

具体实现代码

#include<iostream>
#include<string>
using namespace std;
typedef struct BiTNode
{char data;struct BiTNode* lchild,* rchild;
}BiTNode,*BiTree;
BiTNode* MakeNode(char data)
{BiTNode* node = new BiTNode;node->data = data;node->lchild = NULL;node->rchild = NULL;return node;
}
void inOrder(BiTree root)
{if (root != NULL){inOrder(root->lchild);cout << root->data<<" ";inOrder(root->rchild);}
}
void MakeTree(BiTNode*& root)
{char x;if(!(cin >> x)){ root=NULL; return; }if (x == '#'){root = NULL;}else{root = MakeNode(x);MakeTree(root->lchild);MakeTree(root->rchild);}
}
void DestroyTree(BiTNode*& root) {if (root) {DestroyTree(root->lchild);DestroyTree(root->rchild);delete root;root = NULL;}
}
int main()
{while (true){BiTNode* root = NULL;MakeTree(root);// 读不到树了就退出if(root == NULL) break;inOrder(root);cout << endl;DestroyTree(root);}return 0;
}

题目2：先序输出叶子结点

函数代码

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);//遍历右子树
}

题目3：求树的高度

函数代码

int GetHeight( BinTree BT )
{if(BT==NULL){return 0;}int leftH=GetHeight(BT->Left);int rightH=GetHeight(BT->Right);//采用递归计算，左右子树高度较高的那一边+1return (leftH>rightH ? leftH : rightH)+1;
}

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

主要函数伪代码

二叉树结构体  BiNode
函数 创建新节点 BiTree MakeNode(char x)
函数 创建树BiTree CreateBTree(string str)//读取字符串
{长度 n = str.size()字符串为空||str[0]!='#'，返回NULL创建数组BiTree* nodes，通过下标映射来存储左右孩子 for循环：i 的左孩子是2i，右孩子 是2i+1//连接左右孩子nodes[i]->left=nodes[left]nodes[i]->right=nodes[right]返回 root
}
函数 获取树高int GetHight(BiTree T)
函数 层序遍历void LevelOrder(BiTree T)如果!T,输出NULL并return;创建队列<BiTree>，根节点入队int first = 1 (格式化输出)循环: (!queue.empty())如果cur = queue.front()，出队如果是first，输出data否则 输出 空格+data如果(curr->left) 入队如果(curr->right) 入队}

具体实现代码

#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef struct BiNode
{char data;struct BiNode* left;struct BiNode* right;
}BiNode,*BiTree;BiTree MakeNode(char x)
{BiTree node =new BiNode;node->data=x;node->left =node->right=NULL;return node;
}
BiTree CreateBTree(string str)
{int n= str.size();if(n == 0 || str[0] != '#'){return NULL;}// 数组映射法：i 的左孩子 2i，右孩子 2i+1BiTree* nodes = new BiTree[n];for (int i = 0; i < n; i++){if (str[i] == '#'){nodes[i] = NULL;} else{nodes[i] = MakeNode(str[i]);}}//连左右孩子for (int i = 1; i < n; i++){// 根从下标1开始（因为0是#）if (nodes[i] == NULL) continue;int left = 2 * i;int right = 2 * i + 1;if (left < n) nodes[i]->left = nodes[left];if (right < n) nodes[i]->right = nodes[right];}BiTree root = nodes[1];//下标1是真正根delete[] nodes;// 释放数组return root;
}
int GetHight(BiTree T)
{if(!T) return 0;int LeftH=GetHight(T->left);int RightH=GetHight(T->right);return( LeftH>RightH )? LeftH+1:RightH+1;
}
void LevelOrder(BiTree T)
{if(!T){cout << "NULL";return;}queue<BiTree> q;q.push(T);int first = 1;while(!q.empty()){BiTree curr = q.front();q.pop();if(first){cout << curr->data;first = 0;}else{cout << " " << curr->data;}if(curr->left) q.push(curr->left);if(curr->right) q.push(curr->right);}
}
int main()
{string str;cin>>str;BiTree T=CreateBTree(str);LevelOrder(T);cout<<endl;return 0;
}

题目5：创建二叉排序树(中序输出、插入、删除):给定数据

(50 30 80 20 40 90 10 25 35 85 23 88)
伪代码

具体实现逻辑大体与题目1类似，故不再详细讲述
//创建二叉树(略不同)
void InsertBST(BiTree& root, int x)
{
//创建根节点 root=MakeNode(x)
如果x < root->data插入左子树 
如果x > root->data插入右子树
}
//删除树的某节点
bool DeleteBST(BiTree& root, int x)
{//只有左子树 递归DeleteBST(root->left)//只有右子树递归DeleteBST(root->right)//左右孩子均有比较x与左右孩子的大小，找到前驱节点并删除
}

具体实现代码

#include <iostream>
#include <string>
using namespace std;
typedef struct BiTNode
{int data; struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;
BiTNode* MakeNode(int data)
{BiTNode* node = new BiTNode;node->data = data;node->lchild = NULL;node->rchild = NULL;return node;
}
void InsertBST(BiTree& root, int x)
{if (root == NULL){root = MakeNode(x); }else if (x < root->data){InsertBST(root->lchild, x); }else if (x > root->data){InsertBST(root->rchild, x); }
}
bool DeleteBST(BiTree& root, int x)
{if (root == NULL) return false;if (x < root->data)return DeleteBST(root->lchild, x);else if (x > root->data)return DeleteBST(root->rchild, x);else {BiTNode* p = root;if (root->lchild == NULL){root = root->rchild;delete p;}else if (root->rchild == NULL){root = root->lchild;delete p;}else{BiTNode* q = root->lchild;while (q->rchild) q = q->rchild;root->data = q->data;DeleteBST(root->lchild, q->data);}return true;}
}
void inOrder(BiTree root)
{if (root != NULL){inOrder(root->lchild);cout << root->data << " ";inOrder(root->rchild);}
}
void DestroyTree(BiTNode*& root) {if (root) {DestroyTree(root->lchild);DestroyTree(root->rchild);delete root;root = NULL;}
}
int main()
{int x;BiTNode* root = NULL;while (cin >> x) {InsertBST(root, x);}inOrder(root);cout << endl;DestroyTree(root);return 0;
}

题目6：hash表、平衡树的应用——航空公司VIP客户查询

主要函数伪代码

  创建哈希表，键值对<key,value> +表名循环(N条飞行记录){匹配ID，累加总飞行里程若飞行小于最小里程K ，add=kelse add=此次飞行里程}查找M个人的飞行记录{如果找不到cout << "No Info" << endl;找到就cout 客户id}

具体实现代码

#include <iostream>
#include <string>
#include <unordered_map> // 哈希表头文件
using namespace std;int main()
{// string（在前面） 是 key（键），int（在后面） 是 value（值），创建的是键值对unordered_map<string, int> myMap;int N, K;cin >> N >> K;for (int i = 0; i < N; i++){string id;int d;cin >> id >> d;int add;if (d < K)add = K;elseadd = d;myMap[id] = myMap[id] + add;  //累加里程，hash表的累加操作}int M;cin >> M;//遍历查找for (int i = 0; i < M; i++){string id;cin >> id;if (myMap.find(id) == myMap.end()){cout << "No Info" << endl;}else{cout << myMap[id] << endl;}}return 0;
}