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

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

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

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

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

二、实验内容与设计思想

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

主要函数伪代码

二叉树结构体BiTNode
//创建新节点
 BiTNode* MakeNode(char data)
//创建二叉树 
void MakeTree(BiTNode & root)
{
    输入x
    root=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 root
    root = 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);
    //采用递归计算，左右子树高度较高的那一边+1
    return (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+1
    BiTree* 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=k
    else 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;
        else
            add = 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;
}

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

操作系统：Windows 10 专业版
编程语言：C++
开发工具：Visual Studio 2022
编译器：vs2022默认编译器、pta

四、实验步骤和调试过程

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

PTA提交截图

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

PTA提交截图

题目3：求二叉树的高度

PTA提交截图

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

PTA提交截图

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

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

本机运行截图

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

PTA提交截图

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

遇到的问题及解决方法：

问题：代码注释冗余，伪代码表意不够清楚。

解决方法：借助ai辅助优化出一个有条理逻辑的注释。

问题：PTA测试点一直过不了。

解决方法：把层序读取字符改成数组映射二叉树左右孩子，通过了测试点。

实验体会和收获：

学会了如何正确用注释表达要编写的代码什么意思，如何用伪代码解释思路。
掌握了树的创建、遍历、插入、删除的基本操作。
对于哈希表的运用还是很不熟练，只掌握了利用自带头文件创建哈希表，累加和查找匹配的基本操作原理，仍需要继续练习思考掌握

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

posted @ 2026-05-13 14:45 豆芽菜zzzz 阅读(15) 评论(0) 收藏举报

刷新页面返回顶部

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

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

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

二、实验内容与设计思想

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

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

题目3：求树的高度

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

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

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

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

四、实验步骤和调试过程

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

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

题目3：求二叉树的高度

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

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

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

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

遇到的问题及解决方法：

实验体会和收获：

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

公告