二叉树的操作（C++实现）

目录

⚽实现要求：

🏐题目分析： 

🏀代码展示：

📌前提类和函数声明：

🥎模块一（层次—>创建二叉树）：

🎱模块二（三种遍历方式、求树结点数目、求树高）：

❄️模块三（前序中序创建树、层次遍历树）： 

📌完整代码展示（建议先把分模块的代码搞清楚）： 

💓 最后：

⚽实现要求：

  • 实验目的

掌握二叉树的基本概念，二叉树的存储结构使用链表。

  • 实验内容
  1. 输入一个完全二叉树的层次遍历字符串，创建这个二叉树，输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个结果独立一行显示)。
  2. 输入二叉树前序序列和中序序列(各元素各不相同)，创建这个二叉树，输出该二叉树的后序序列、层次遍历。

🏐题目分析： 

简单来说实验就是要我们实现三个东西：

一、根据完全二叉树的层次遍历字符串创建这个二叉树。这里这个完全二叉树非常关键，因为如果是一般的二叉树，仅仅有一个层次遍历序列是不能唯一确定一棵二叉树的。

二、前序、中序、后序遍历这个二叉树，然后计算结点数目以及二叉树的高度。这里计算结点数目非常容易，而计算二叉树的高度本质也就是后序遍历的变形。

三、通过一个二叉树的前序序列和中序序列来创建一个二叉树，并后序、层次遍历这个二叉树。这里考察的就是1、根据两个序列创建树。2、层次遍历一棵树

🏀代码展示：

前提类和函数声明：

#include<iostream>
#include<queue>
using namespace std;

int size=0;
char result[1000];

class TreeNode{//树中的每一个结点类
public:
    char data;
    TreeNode* leftN;
    TreeNode* rightN;
public:
    TreeNode(){
        data=' ';
        leftN=NULL;
        rightN=NULL;
    }
    TreeNode(char a){
        data=a;
        leftN=NULL;
        rightN=NULL;
    }
    TreeNode(char a,TreeNode* l,TreeNode* r){
        data=a;
        leftN=l;
        rightN=r;
    }
};
TreeNode* mTree_pre_in(string a,string s);//两个序列创建树的函数声明
class Tree{//树本身的类
public:
    TreeNode* root;
public:
    Tree(string a,int length){
        if(length<=0)return;
        root=new TreeNode(a[1]);
        createTree(root,1,a);
    }
    Tree(){
        root=NULL;
    }
    Tree(TreeNode* t){
        root=t;
    }
//对树的操作放在树这个类里面
    void createTree(TreeNode* a,int index,string s);//根据层次序列构造树
//下面的遍历函数的参数a表示从哪个位置开始遍历
    void preOrder(TreeNode* a);
    void inOrder(TreeNode* a);
    void proOrder(TreeNode* a);
    void levelOrder(TreeNode* a);
    int height(TreeNode* a);//求树的高度

};

🥎模块一（层次—>创建二叉树）：

//s就是层次序列，index表示从哪个下标结点开始创建（我们肯定是从1开始）
void Tree::createTree(TreeNode* a,int index,string s){
    int length=s.size();
    if(2*index<length){//2*index得到的就是目前index下标对应结点的左节点
        TreeNode* t=new TreeNode(s[index*2]);
        a->leftN=t;
        createTree(a->leftN,index*2,s);
    }
    if(index*2+1<length){2*index+1//得到的就是目前index下标对应结点的右节点
        TreeNode* t=new TreeNode(s[index*2+1]);
        a->rightN=t;
        createTree(a->rightN,index*2+1,s);
    }
}

🎱模块二（三种遍历方式、求树结点数目、求树高）：

//所有遍历的结果存储在result中，注意result应该是一个全局遍历而不是临时变量
//size表示目前result中元素的数目，必须是全局变量，并且在每次遍历后下一个遍历前都要重置为0
void Tree::preOrder(TreeNode* a){//前序遍历
    if(a!=NULL){
        result[size++]=a->data;
        preOrder(a->leftN);
        preOrder(a->rightN);
    }
}
void Tree::inOrder(TreeNode* a){//中序遍历
    if(a!=NULL){
        inOrder(a->leftN);
        result[size++]=a->data;
        inOrder(a->rightN);
    }
}
void Tree::proOrder(TreeNode* a){//后序遍历
    if(a!=NULL){
        proOrder(a->leftN);
        proOrder(a->rightN);
        result[size++]=a->data;
    }
}
int Tree::height(TreeNode* a){
    if(a==NULL)//空结点的树高为0，即叶子结点下面的结点高为0
    return 0;//递归一定要有终止的地方
    else{//每一步重复操作就是递归使用的本质原因
        int leftHeight=height(a->leftN);
        int rightHeight=height(a->rightN);
        if(leftHeight>rightHeight)return ++leftHeight;
        else return ++rightHeight;
    }
}

❄️模块三（前序中序创建树、层次遍历树）： 

//层次遍历树用到了队列这个数据结构，这里不过多解释
void Tree::levelOrder(TreeNode* a){
    if(a==NULL)
        return;
    TreeNode* t=a;
    queue<TreeNode*> q;
    q.push(a);
    while(!q.empty()){
        t=q.front();
        result[size++]=t->data;
        q.pop();
        if(t->leftN)q.push(t->leftN);
        if(t->rightN)q.push(t->rightN);
    }
}
//每次能分析出一个根节点加上左右子树的前后序列，所以每次可以添加一个结点
//创建树的本质就是创建新的结点在合适的位置
TreeNode* mTree_pre_in(string pre,string in,int length){
    if(length==0)//如果前后序列为零，则不用创建
    return NULL;
//前序的第一个元素必定是树的根结点
    TreeNode* root=new TreeNode(pre[1]);
    int count=0;
//找到这个根节点在中序序列中的位置，因为中序序列根节点两边分别是左右子树
    for(int i=1;i<=length;i++){
        if(in[i]==pre[1])
        count=i;
    }
//得到左右子树的长度
    int leftLength=count-1;
    int rightLength=length-count;
//下面“1”+操作是为了让我们每次都是从下标1开始。主要为了方便树的操作
//下面就是分别对左右子树进行递归操作
//分析可得这个操作是前序遍历的一个变型
    if(count!=0){
        root->leftN=mTree_pre_in("1"+pre.substr(2,leftLength),"1"+in.substr(1,leftLength),leftLength);
        root->rightN=mTree_pre_in("1"+pre.substr(2+leftLength,rightLength),"1"+in.substr(count+1,rightLength),rightLength);
    }
    return root;

}

📌完整代码展示（建议先把分模块的代码搞清楚）： 

#include<iostream>
#include<queue>
using namespace std;

int size=0;
char result[1000];

class TreeNode{
public:
    char data;
    TreeNode* leftN;
    TreeNode* rightN;
public:
    TreeNode(){
        data=' ';
        leftN=NULL;
        rightN=NULL;
    }
    TreeNode(char a){
        data=a;
        leftN=NULL;
        rightN=NULL;
    }
    TreeNode(char a,TreeNode* l,TreeNode* r){
        data=a;
        leftN=l;
        rightN=r;
    }
};
TreeNode* mTree_pre_in(string a,string s);
class Tree{
public:
    TreeNode* root;
public:
    Tree(string a,int length){
        if(length<=0)return;
        root=new TreeNode(a[1]);
        createTree(root,1,a);
    }
    Tree(){
        root=NULL;
    }
    Tree(TreeNode* t){
        root=t;
    }
    void createTree(TreeNode* a,int index,string s);
    void preOrder(TreeNode* a);//下面的遍历函数的参数a表示从哪个位置开始遍历
    void inOrder(TreeNode* a);
    void proOrder(TreeNode* a);
    void levelOrder(TreeNode* a);
    int height(TreeNode* a);

};
TreeNode* mTree_pre_in(string pre,string in,int length){//每次能分析出一个根节点加上左右子树的前后序列，所以每次可以添加一个结点
    if(length==0)//如果前后序列为零，则不用创建
    return NULL;
    TreeNode* root=new TreeNode(pre[1]);
    int count=0;
    for(int i=1;i<=length;i++){
        if(in[i]==pre[1])
        count=i;
    }
    int leftLength=count-1;
    int rightLength=length-count;
    if(count!=0){
        root->leftN=mTree_pre_in("1"+pre.substr(2,leftLength),"1"+in.substr(1,leftLength),leftLength);
        root->rightN=mTree_pre_in("1"+pre.substr(2+leftLength,rightLength),"1"+in.substr(count+1,rightLength),rightLength);
    }
    return root;

}
int Tree::height(TreeNode* a){
    if(a==NULL)//空结点的树高为0，即叶子结点下面的结点高为0
    return 0;//递归一定要有终止的地方
    else{//每一步重复操作就是递归使用的本质原因
        int leftHeight=height(a->leftN);
        int rightHeight=height(a->rightN);
        if(leftHeight>rightHeight)return ++leftHeight;
        else return ++rightHeight;
    }
}
void Tree::createTree(TreeNode* a,int index,string s){
    int length=s.size();
    if(2*index<length){
        TreeNode* t=new TreeNode(s[index*2]);
        a->leftN=t;
        createTree(a->leftN,index*2,s);
    }
    if(index*2+1<length){
        TreeNode* t=new TreeNode(s[index*2+1]);
        a->rightN=t;
        createTree(a->rightN,index*2+1,s);
    }
}
void printNode(char result[],int size){
    for(int i=0;i<size-1;i++){
        cout<<result[i]<<",";
    }
    cout<<result[size-1]<<endl;
}
void Tree::preOrder(TreeNode* a){
    if(a!=NULL){
        result[size++]=a->data;
        preOrder(a->leftN);
        preOrder(a->rightN);
    }
}
void Tree::inOrder(TreeNode* a){
    if(a!=NULL){
        inOrder(a->leftN);
        result[size++]=a->data;
        inOrder(a->rightN);
    }
}
void Tree::proOrder(TreeNode* a){
    if(a!=NULL){
        proOrder(a->leftN);
        proOrder(a->rightN);
        result[size++]=a->data;
    }
}
void Tree::levelOrder(TreeNode* a){
    if(a==NULL)
        return;
    TreeNode* t=a;
    queue<TreeNode*> q;
    q.push(a);
    while(!q.empty()){
        t=q.front();
        result[size++]=t->data;
        q.pop();
        if(t->leftN)q.push(t->leftN);
        if(t->rightN)q.push(t->rightN);
    }
}
int main(){
    cout<<"Input1"<<endl;
    string s;
    cin>>s;
    cout<<"Output1"<<endl;
    string a="1"+s;
    int length=a.size();
    Tree tree(a,length);
    tree.preOrder(tree.root);//前序遍历
    printNode(result,size);
    size=0;
    tree.inOrder(tree.root);//中序遍历
    printNode(result,size);
    size=0;
    tree.proOrder(tree.root);//后序遍历
    printNode(result,size);
    size=0;

    int nodeNum=s.size();
    int height1=tree.height(tree.root);
    cout<<nodeNum<<endl;
    cout<<height1<<endl;

    cout<<"Input2"<<endl;
    string s1;
    cin>>s1;
    string s2;
    cin>>s2;
    cout<<"Output2"<<endl;
    s1="1"+s1;
    s2="1"+s2;
    int l=s1.size()-1;
    TreeNode* t=mTree_pre_in(s1,s2,l);
    Tree tree2(t);
    tree2.proOrder(tree2.root);
    printNode(result,size);
    size=0;
    tree2.levelOrder(tree2.root);
    printNode(result,size);
    size=0;

    cout<<"End"<<endl;
}

💓 最后总结：

最后总结与感悟

本题要求完成的是数据结构中的树结构，包括树的生成、树的遍历、树高的求解等，树的生成包括给定层次遍历序列生成、给定中序和前序序列生成。

首先明确一个点，树的结构和递归脱不开关系，也就是说树中的操作很多时候都是靠递归方法去解决的，树的整个结构就是一个递归结构。

  1. 树层次遍历序列下的生成。给定一个层次遍历序列，我们是能够唯一生成一颗树的。从递归角度思考如何生成。生成的本质就是创建结点，由于实际上每个结点的值和位置在string层次遍历序列中我们都以及了解了，所以我们就可以思考一下创建整个过程的一个子过程：从外界创建一个根节点，然后生成并链接它的左右子结点。 接下来对刚刚生成的左右子节点做同样的操作，去链接生成他们的左右子节点。一次次递归，问题就得以解决。

总的来说就是1、整体过程是生成一棵树 2、子过程是对每一个结点生成并链接它的左右结点。如此，子过程不断重复整个树便可以形成

  1. 树的遍历分为前序中序和后序遍历。其核心思想就是在于什么时候输出结点，总共就三条语句。1、整体过程是遍历一整棵树。2、整体问题可以分解为访问左子树+访问右子树+对当前结点的访问。而遍历左子树、右子树的问题又能继续分为这三个子问题。而这三个问题的处理顺序就决定了我们遍历的顺序。
  2. 求解树高同样也是递归解决。1、整体问题是求解这棵树的树高。2、整体问题可以分解为求解其左右子树的树高，选取其中高的那个加1作为整体的树高。然后求解左右子树的树高问题又能做上面的分解。所以整体上又是一个递归重复的问题
  3. 树在给前中序序列下的生成。1、整体来看生成树的本质就是不停地生成新的结点。2、而生成结点同样可以分解为许多子问题。子问题的重复能够解决整体问题。3、子问题为：根据前序序列的第一个结点确定整棵树的根节点，同时生成这个根节点。并且根据中序序列，确定这棵树的左子树与右子树的元素。然后让根节点连接上生成的左子树与右子树。生成左右子树的方法和生成整体的相同，左右子树也看成一个独立树去生成。

注意的点：

  1. 在编写程序的过程中要注意一个点：递归是会不停重复函数，所以对于一些我们希望在递归过程中不要发生改变的量，我们应该定义并在函数外面进行赋值。例如结点个数size变量。一次printf操作，这些都是我们只希望在递归结束后执行一次的，所以不要放在递归内部
  2. 由于是树的操作，我们希望从下标为1开始。而我们读入string是从下标为0开始的，所以我们可以通过“1”+c这种方式，让string从下标1开始才有效。

创作不易，如果觉得内容不错，收藏一下呗，小猫求求了~

真的真的不行，就给个免费的赞吧~~ 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/207252.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

QT Creator 保存(Ctrl+S)时，会将Tab制表符转换为空格

QT Creator 保存(Ctrl+S)时，会将Tab制表符转换为空格

今天在写makefile文件时&#xff0c;发现QT Creator 保存(CtrlS)时&#xff0c;会将Tab制表符转换为空格&#xff0c;之前没有发现&#xff0c;略坑&#xff0c;官网上也有说明&#xff0c;点这里 简单来说&#xff0c;解决办法如下 依次点击&#xff1a;Tools ->Options-&g…
阅读更多...
C51--DHT11数据读取

C51--DHT11数据读取

DHT11传输0的时序分析&#xff1a; DHT11传输1的时序分析&#xff1a; 用while(dht)卡点&#xff0c;当不满足while时&#xff0c;信号拉低&#xff1b; 用while(&#xff01;dht)卡点&#xff0c;当不满足while时&#xff0c;信号拉高。 传输0和1时有效数据都是高电平&…
阅读更多...
每日一题：LeetCode-1089. 复写零

每日一题：LeetCode-1089. 复写零

每日一题系列&#xff08;day 09&#xff09; 前言&#xff1a; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f50e…
阅读更多...
Linux：服务器管理工具宝塔（bt）安装教程

Linux：服务器管理工具宝塔（bt）安装教程

一、简介 bt宝塔Linux面板是提升运维效率的服务器管理软件&#xff0c;支持一键LAMP/LNMP/集群/监控/网站/FTP/数据库/JAVA等多项服务的管理功能 二、安装 使用 SSH 连接工具&#xff0c;如堡塔SSH终端连接到您的 Linux 服务器后&#xff0c;挂载磁盘&#xff0c;根据系统执…
阅读更多...
微信如何单独隐藏某个人的聊天记录？

微信如何单独隐藏某个人的聊天记录？

微信&#xff0c;如今已成为我们生活中不可或缺的沟通工具&#xff0c;它的应用范围涵盖了工作、学习及日常生活的方方面面。然而&#xff0c;有时为了保护个人隐私&#xff0c;或是不愿让他人看到特定对话&#xff0c;我们需要对与某人的聊天记录进行隐藏。那么&#xff0c;微…
阅读更多...
【已解决】如何打开设置了密码的7Z压缩文件？

【已解决】如何打开设置了密码的7Z压缩文件？

7Z是一种常见的压缩文件格式&#xff0c;相比RAR和ZIP格式&#xff0c;它的压缩率更高&#xff0c;可以压缩出更小的文件体积&#xff0c;也同样可以设置密码保护&#xff0c;那设置了密码的7Z压缩文件要如何打开呢&#xff1f; 我们知道&#xff0c;7Z压缩文件设置密码保护后…
阅读更多...
06-Git分支相关的命令,如创建/删除/切换分支

06-Git分支相关的命令,如创建/删除/切换分支

Git分支(副本) 在版本控制过程中需要同时推进多个任务,此时可以为每个任务创建单独分支即开一个一模一样的副本 ,最终分支开发完后再合并到主分支提高开发效率 使用分支意味着程序员可以把自己的工作从开发主线上分离开来&#xff0c;开发自己分支的时候不会影响主线分支的运…
阅读更多...
Linux命令--根据端口号查看进程号（PID）

Linux命令--根据端口号查看进程号（PID）

Linux命令–根据端口号查看进程号&#xff08;PID&#xff09; 查找8080端口对应的进程号: netstat -nlp|grep :8297对应的进程号1061,如果想杀掉此进程&#xff0c;可以用一下命令&#xff1a; kill -9 1061
阅读更多...
2023年中国金融租赁行业研究报告

2023年中国金融租赁行业研究报告

第一章 行业概况 1.1 定义 金融租赁是一种融资方式&#xff0c;其中租赁公司&#xff08;出租人&#xff09;为企业&#xff08;承租人&#xff09;购买所需设备&#xff0c;并在租赁期内由承租人使用。承租人负责支付租金&#xff0c;租赁期满后有权选择退租、续租或购买设备…
阅读更多...
Java中重载和重写的区别

Java中重载和重写的区别

1.重写(Override) 从字面上看&#xff0c;重写就是重新写一遍的意思。其实就是在子类中把父类本身有的方法重新写一遍。子类继承了父类原有的方法&#xff0c;但有时子类并不想原封不动的继承父类中的某个方法&#xff0c;所以在方法名&#xff0c;参数列表&#xff0c;返回类型…
阅读更多...
【机器学习】集成学习算法之AdaBoost

【机器学习】集成学习算法之AdaBoost

文章目录 基本步骤示例生成第 1 棵决策树生产第 2 棵决策树生成第 T 棵决策树加权投票 sklearn 实现 基本步骤 首先&#xff0c;是初始化训练数据的权值分布 D 1 D_1 D1​。假设有 m m m 个训练样本数据&#xff0c;则每一个训练样本最开始时&#xff0c;都被赋予相同的权值…
阅读更多...
爬虫从入门到精通(21) |字体加密通杀方案

爬虫从入门到精通(21) |字体加密通杀方案

文章目录 一、了解什么是字体加密二、Python打开字体加密文件三、字体加密的通杀1.静态的字体文件固定顺序的字体2.其他动态变化情况 一、了解什么是字体加密 字体加密是页面和前端字体文件想配合完成的一个反爬策略。通过css对其中一些重要数据进行加密&#xff0c;使我们在代…
阅读更多...
启用Android放大镜功能，事半功倍，可惜该功能只存在于Android 14

启用Android放大镜功能，事半功倍，可惜该功能只存在于Android 14

安卓屏幕放大镜是一种无障碍功能&#xff0c;旨在通过放大屏幕上显示的内容来帮助任何有视力障碍的人。这是安卓提供的几个功能之一&#xff0c;旨在使智能手机更具包容性和用户友好性。 如果你曾经想知道如何在你的安卓手机上设置并充分利用屏幕放大镜&#xff0c;那么你就来…
阅读更多...
索尼mxf覆盖部分恢复案例(索尼PMW-580)

索尼mxf覆盖部分恢复案例(索尼PMW-580)

索尼mxf覆盖部分恢复案例(索尼PMW-580) 索尼的摄像机型号是比较繁多的&#xff0c;高端系列基本上是以mxf文件为主&#xff0c;这一类案例之前处理不少&#xff0c;今天我们看一个索尼pmw-580摄像机删除后又覆盖的恢复案例。 故障存储:64G SD卡/Exfat文件系统 故障现象: 拍…
阅读更多...
Java核心知识点整理大全25-笔记

Java核心知识点整理大全25-笔记

目录 25. Hadoop 25.1.1. 概念 25.1.2. HDFS 25.1.2.1. Client 25.1.2.2. NameNode 25.1.2.3. Secondary NameNode 25.1.2.4. DataNode 25.1.3. MapReduce 25.1.3.1. Client 25.1.3.2. JobTracker 25.1.3.3. TaskTracker 25.1.3.4. Task 25.1.3.5. Reduce Task 执行…
阅读更多...
理解Gamma传递函数

理解Gamma传递函数

对于任何认真从事色彩工作或电影和电视母带处理的人来说&#xff0c;掌握Gamma编码是一项重要的知识&#xff0c;但它也可能是最令人困惑的主题之一&#xff0c;因为我们人类的视力与大多数电子设备的工作方式截然不同。 Gamma编码和传递函数的全部工作都是基于向我们的人眼提供…
阅读更多...
【深度学习】gan网络原理生成对抗网络

【深度学习】gan网络原理生成对抗网络

【深度学习】gan网络原理生成对抗网络 GAN的基本思想源自博弈论你的二人零和博弈&#xff0c;由一个生成器和一个判别器构成&#xff0c;通过对抗学习的方式训练&#xff0c;目的是估测数据样本的潜在分布并生成新的数据样本。 1.下载数据并对数据进行规范 transform tran…
阅读更多...
用Python进行gRPC接口测试(一)

用Python进行gRPC接口测试(一)

前言 gRPC 是一个高性能、通用的开源RPC框架&#xff0c;其由 Google 主要面向移动应用开发并基于HTTP/2 协议标准而设计&#xff0c;基于 ProtoBuf(Protocol Buffers) 序列化协议开发&#xff0c;且支持众多开发语言。 自gRPC推出以来&#xff0c;已经广泛应用于各种服务之中…
阅读更多...
UI自动化测试工具有哪些优势?

UI自动化测试工具有哪些优势?

UI自动化测试工具通过提高测试效率、覆盖率&#xff0c;减少测试时间和成本&#xff0c;以及支持持续集成等方式&#xff0c;为软件开发团队提供了一系列重要的优势&#xff0c;有助于提升软件质量和开发效率。 自动化执行&#xff1a;UI自动化测试工具可以模拟用户与应用程序的…
阅读更多...
ubuntu22下使用nvidia 2080T显卡部署pytorch

ubuntu22下使用nvidia 2080T显卡部署pytorch

1.直接到NVIDA官网下载相应的驱动&#xff0c;然后安装官方驱动 | NVIDIA 2.下载相应版本cuda&#xff0c;并安装&#xff0c;安装时不安装驱动 3.conda install pytorch2.1.0 torchvision0.16.0 torchaudio2.1.0 pytorch-cuda12.1 -c pytorch -c nvidia 安装pytorch。 安装…
阅读更多...
最新文章

Copyright @ 2022~2023