(紫书自学系列)P150树的层次遍历(Trees on the level,UVa 122)(C++)

news/2024/4/20 13:35:58/

通过例题学习对树的相关操作,为BFS和DFS打好基础,以刘佬给的代码为准,加些解释以便理解。(本题刘佬提出内存泄漏的情况,本文未提及,若有需要请自行阅读书本)

文章目录

  • 前言
  • 一、题目
  • 二、问题分析
  • 完整代码


前言

第五章:大致码完书上STL的题(不会的看题解,最起码题解看懂,看不懂也没事)先理解STL的一些基本内容就好后面刷题再补

第六章:6.1和6.2 快速过一遍,看例题,自己动手敲敲就好了

6.3就是梦的开始,BFS与DFS用的地方很广,我个人认为这一章DFS和BFS最为重要,看的时候要扣好每个细节。


一、题目

树状结构在电脑科学的许多领域中都相当重要。本问题牵涉到建立树及遍历树。

 

下为输入输出的案例:

输入:

(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

输出:

5 4 8 11 13 4 7 2 1
not complete

二、问题分析

该题需要注意的是,我们不仅仅只是构造树然后遍历输出

题目指出,输入的数据可能不构成树(分为两种情况):

  • 有某些该有的节点没有给

  • 有某些节点重复给

数据读入即为一个难点

我们在读入节点的时候,将其存到树中,下面为“数据读入函数”

char s[maxn];bool read_input()                                 
{failed = false;                               //root = newnode();                             //创造树的根节点for(;;)                                       //每组数据为一个循环,如(11,LL){                                           if(scanf("%s", s) != 1) return false;     //scanf只要读入字符串,函数结果就为1,读入空则为0,使得每次循环处理一个数据if(!strcmp(s, "()")) break;               //结束标志int v;                                      sscanf(&s[1], "%d", &v);                   //该处sscanf函数为从字符串中提取第一个数字存到v中,即将要处理的数据给vaddnode(v, strchr(s, ',')+1);              //addnode函数需要我们定义,将需要处理的数据按“,”后面的字母(如“L”)进行处理}return true;
}

关于树的建立如下

struct Node
{bool have_value;             //作为一个标记,判断该结点是否被赋值int num;                     //该结点存入的数据Node *left,*right;           Node()                       //养成结点初始化为空的习惯{have_value=false;left=NULL;right=NULL;};
};

在每次处理一个新数据时,我们需要对树进行扩展,因此,我们还需要一个构造树结点的函数(用到new函数,申请空间并构造函数,如果空间不足则返回NULL):

Node* newnode()
{return new Node();
}

对于“数据读入函数”中的addnode函数,我们进行如下定义:

    void addnode(int v,char* s)                     //传入处理的数据v和字符串s(s是从原s的逗号后面第一个字符开始的){int n=strlen(s);                            //n为长度Node* u=root;                               //根结点root的地址为ufor(int i=0; i<n; i++){if(s[i]=='L')                            //读到”L“时候,当前结点的左结点若为空,则建一个,当前的u为之前的u指向的左结点{if(u->left==NULL) u->left=newnode;u=u->left;}else{if(s[i]=='R')                         //读到”R“时同理{if(u->right==NULL)u->right=newnode();u=u->right;}}}if(u->have_value) failed=true;                 //若该结点已被赋值u->num=v;                                       //当前u为数据v应该在的位置,数据v赋给它对应u结构体的数据numu->have_value=true;                         //别忘了标记该结点为已赋值}

最难的部分已经结束了,现在只要用队列实现BFS离AC不远了

    bool BFS(vector<int>& ans)                       //用ans来存输出数据{queue<Node*> q;ans.clear();                                 //ans清空别忘了q.push(root);                                //队列q,从根结点root开始排队while(!q.empty()){Noede* u=q.front();                      //对即将出队的头部结点的子结点进行遍历q.pop();if(!u->have_value) return false;         //如果该结点没有赋值,则说明输入有误ans.push_back(u->num);                     //父结点访问if(u->left!=NULL) q.push(u->left);       //如果左结点非空,则将其入队if(u->right!=NULL) q.push(u->right);}return true;}

三.完整代码

#include <iostream>
#include<vector>
#include<queue>
#include<cstring>
#define maxn 1001000
using namespace std;struct Node
{bool have_value;int num;Node *left,*right;Node(){have_value=false;left=NULL;right=NULL;};
};
char s[maxn];
bool failed=false;
int num;
Node* root;
Node* newnode()
{return new Node();
}bool BFS(vector<int>& ans)                       //用ans来存输出数据
{queue<Node*> q;ans.clear();                                 //ans清空别忘了q.push(root);                                //队列q,从根结点root开始排队while(!q.empty()){Node* u=q.front();                      //对即将出队的头部结点的子结点进行遍历q.pop();if(!u->have_value) return false;         //如果该结点没有赋值,则说明输入有误ans.push_back(u->num);                     //父结点访问if(u->left!=NULL) q.push(u->left);       //如果左结点非空,则将其入队if(u->right!=NULL) q.push(u->right);}return true;
}void addnode(int v,char* s)                     //传入处理的数据v和字符串s(s是从原s的逗号后面第一个字符开始的)
{int n=strlen(s);                            //n为长度Node* u=root;                               //根结点root的地址为ufor(int i=0; i<n; i++){if(s[i]=='L')                            //读到”L“时候,当前结点的左结点若为空,则建一个,当前的u为之前的u指向的左结点{if(u->left == NULL) u->left=newnode();u=u->left;}else{if(s[i]=='R')                         //读到”R“时同理{if(u->right==NULL)u->right=newnode();u=u->right;}}}if(u->have_value) failed=true;                 //若该结点已被赋值u->num=v;                                       //当前u为数据v应该在的位置,数据v赋给它对应u结构体的数据numu->have_value=true;                         //别忘了标记该结点为已赋值
}bool read_input()
{failed =false;root = newnode();for(;;){if(scanf("%s", s) != 1) return false;if(!strcmp(s, "()")) break;int v;sscanf(&s[1], "%d", &v);addnode(v, strchr(s, ',')+1);}return true;
}int main()
{vector<int> ans;while(read_input()){if(failed||!BFS(ans)){cout<<"not complete";}else{for(vector<int>::iterator t=ans.begin(); t!=ans.end(); t++){if(t!=ans.end()-1){cout<<*t<<" ";}else cout<<*t;}}cout<<endl;}return 0;
}

虽然很好理解树的概念,但一上手就写不了了

还得多练练,不能只看不练 


http://www.ppmy.cn/news/272578.html

相关文章

二叉树——王道真题P149-P150

算法笔记——二叉树 核心&#xff1a;四大非递归&递归遍历算法 非递归不要习惯性地用递归子树思想 非递归一定是一步步的执行逻辑&#xff0c;每一步仅能看到当前。宏观上则需要拿到之前的结点 数据结构定义 typedef char ElemType; //二叉树定义 typedef struct BitN…

Leetcode P150 逆波兰表达式求值

Leetcode P150 逆波兰表达式求值 题目 根据逆波兰表示法&#xff0c;求表达式的值。 有效的运算符包括 , -, *, / 。每个运算对象可以是整数&#xff0c;也可以是另一个逆波兰表达式。 说明&#xff1a; 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说&am…

尚硅谷P140-P150总结

数组的定义&#xff0c;这个就不说了&#xff0c;个人觉得了解就可&#xff0c;数组嘛&#xff0c;肯定就是一组数。然后是数组的初始化&#xff0c;分为静态初始化和动态初始化&#xff0c;这里把一维数组和二位数组一并说 int[] array1 new int[5]{1,2,3,4,5};//这个是静态…

TCP/IP详解(一)

TCP/IP协议是Internet互联网最基本的协议&#xff0c;其在一定程度上参考了七层OSI&#xff08;Open System Interconnect&#xff0c;即开放式系统互联&#xff09;模型 OSI参考模型是国际组织ISO在1985年发布的网络互联模型&#xff0c;目的是为了让所有公司使用统一的规范来…

我们不一样-康耐视visionpro和apple vision pro

​ 机器视觉Halcon-不同颜色快速识别 康耐视Visionpro是美国cognex visionpro。 康耐视 VisionPro 是领先的计算机式视觉软件。它主要用于设置和部署视觉应用 - 无论是使用相机还是图像采集卡。借助 VisionPro,用户可执行各种功能,包括几何对象定位和检测、识别、测量和对准…

vue中的计算属性和侦听器

目录 计算属性使用计算属性只读计算属性可写计算属性 计算属性的缓存 侦听器使用侦听器侦听不同的数据源深度侦听直接给 watch() 传入一个响应式对象使用deep 选项&#xff0c;强制转成深层侦听器 立即侦听watchEffect()watch 和 watchEffect的区别 计算属性和侦听器的异同点相…

华为服务器做系统密码,华为服务器默认密码是多少

华为服务器默认密码是多少 内容精选 换一换 由于root用户拥有最高权限,直接使用root用户登录服务器可能会存在安全风险。建议您使用普通用户登录服务器后切换为root用户,再执行后续安装操作,并建议您通过配置禁止root用户SSH登录的选项,来提升系统安全性。具体配置如下:先…

移动服务密码怎么查_服务密码忘记了怎么办_百度经验

https://jingyan.baidu.com/article/59703552cbed988fc1074056.html

移动修改服务器密码是什么,移动服务器密码

移动服务器密码 内容精选 换一换 只有运行中的弹性云服务器才允许用户登录。Linux操作系统用户名“root”。忘记密码&#xff0c;请先通过“重置密码”功能设置登录密码。重置密码&#xff1a;选中待重置密码的云耀云服务器&#xff0c;并选择“操作”列下的“ 重置密码”。重置…

中国移动家庭智能网关超级账号密码

登陆中国移动智能网关管理员账号。 一般来说都在背面&#xff0c;如果接触不到路由器可使用超级用户名登录 超级账号&#xff1a;CMCCAdmin 超级密码&#xff1a;aDm8H%MdA 超级用户名:telecomadmin 超级密码:nE7jA%5m 用户名 telecomadmin 密码 admintelecom 超级用户名 :…

移动邮箱(139):开启服务+密码登录

移动邮箱&#xff08;139&#xff09;&#xff1a;开启服务密码登录 官网&#xff1a;https://mail.10086.cn/ 帮助&#xff1a;http://help.mail.10086.cn/statichtml/0/Category/223/List_1.html 关联阅读&#xff1a; 139邮箱服务器地址是什么&#xff1f;如何开启POP3和IMA…

计算机默认网络密码是多少,中国电信的默认服务密码是什么

许多小伙伴处理中国电信的业务&#xff0c;有时需要输入密码进行某些设置。每个方向都有一个默认密码。中国电信的默认服务密码是什么&#xff1f;西溪小编将向您介绍。 中国电信的默认服务密码是什么 1、中国电信的移动电话和无线宽带的初始用户的默认密码&#xff1a;11位移动…

中国移动重置服务密码方法

编辑短信&#xff1a; mmcz空格身份证号空格新密码空格再输一遍新密码 发送到10086即可完成。 注意&#xff1a;密码必须是六位数字&#xff0c;本人是北京的号码&#xff0c;可以用这个方法修改

移动手机号服务密码重置

发送 &#xff1a;HFMM空格身份证号码修改后的服务密码&#xff08;6位&#xff09;到10086&#xff0c;即可重置服务密码。

8自由度并联腿机器狗实现行走功能

1. 功能说明 本文示例将实现R309a样机8自由度并联腿机器狗行走的功能。 2. 并联仿生机器人结构设计 机器狗是一种典型的并联仿生四足机器人&#xff0c;其腿部结构主要模仿了四足哺乳动物的腿部结构&#xff0c;主要由腿部的节段和旋转关节组成。在设计机器狗的腿部结构时&…

8g内存和16g内存区别 mac_苹果8g和16g的区别大盘点

导读&#xff1a; 苹果 手机是一款拥有极高知名度的手机品牌&#xff0c;它在中国是一款备受欢迎的手机品牌&#xff0c;苹果品牌的手机在不断的进行创新和改变&#xff0c;每一代苹果手机都有它的优势&#xff0c;每一款苹果手机都有它的特别之处&#xff0c;每一代的苹果手机…

基于最近电平逼近的开环MMC逆变器MATLAB仿真模型

资源地址&#xff1a; 模型介绍&#xff1a; MATLAB21b版本 DC:12kV&#xff0c;N&#xff1d;12&#xff0c; 采用最近电平逼近调制&#xff0c;采用基于排序的均压方法&#xff0c;冒泡排序&#xff0b;桥臂电流方向判断。 连接负载&#xff0c;可以得到13电平相电压波形。…

苹果审核6

注意: 2014年2月初开始&#xff0c;Apple开始拒绝采集IDFA(identifier for advertising)而未集成任何广告服务的应用进入AppStore。 为解决此问题&#xff0c;一般的SDK都为用户提供两个版本的SDK&#xff0c;包括采集IDFA的标准版和不采集IDFA的无IDFA版。 下面是总结的一些…

Python编程:探索无限可能的世界

目录 一、如何学习/自学 Python &#xff1f;二、Python 的练手项目推荐三、Python 入门学习方法和值得推荐的经典教材四、用最短时间高效而踏实地学习 Python五、处理 Python 入门难以进步的现象六、Python 编程&#xff0c;应该养成哪些好的习惯七、对于编程零基础&#xff0…

分布式锁原理与实战四:ZooKeeper分布式锁Java代码实现

目录 ZooKeeper分布式锁的基本实现 实战&#xff1a;加锁的实现 lock&#xff08;&#xff09;方法的实现代码 tryLock&#xff08;&#xff09;尝试加锁 checkLocked&#xff08;&#xff09;检查是否持有锁 可重入的实现代码 释放锁的实现 实战&#xff1a;分布式锁的…