当前位置：首页 > 编程日记 > 正文

PAT（甲级）2019年春季考试 7-4 Structure of a Binary Tree

编程日记 2024-09-05 21:20:00

整体思路

犯的错误

代码

整体思路

1.先根据后序和中序序列建树，老生常谈，记得返回root

2.对树进行BFS，在这个过程中用hash的方式记录下每个值对应的父节点、左孩子、右孩子的值，记录下深度(即层数)，还有孩子的个数。

犯的错误

1. 根据后序和中序建树时，在中序中找父节点的位置

	int i;for(i=inL;i<=inR;i++){if(inSeq[i]==root->v){break;}}

for循环的条件又把声明了一遍int，导致下面直接用i，用的是0。

2. 读入每一句判断时

忘记cin遇到空格即停，应该用getline(cin,str)的

3. 在读入判断个数之后，需要加上cin.get();吸收末尾回车

剩余无需吸收末尾回车，getline(cin,str)能自己处理好，吸收了反而导致后面错读

4. 我把这里说的full binary tree和满二叉树混为一谈，这里是题目自己定义了一个树，就是孩子节点个数要不为0要不为2，而真正满二叉树的定义是每一层的结点个数都达到了该层可以达到的最大个数。

代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>using namespace std;const int maxn = 31;
const int SUP = 1001;int inSeq[maxn],postSeq[maxn];
int parent[SUP],lchild[SUP],rchild[SUP],layer[SUP],childNum[SUP] = {0};struct Node{int v;Node* lchild;Node* rchild;
};void BFS(Node* root){queue<Node*> Q;Q.push(root);layer[root->v] = 1;while(!Q.empty()){Node* now = Q.front();Q.pop();if(now->lchild!=NULL){childNum[now->v] ++;lchild[now->v] = now->lchild->v;parent[now->lchild->v] = now->v;layer[now->lchild->v] = layer[now->v]+1;Q.push(now->lchild);}if(now->rchild!=NULL){childNum[now->v] ++;rchild[now->v] = now->rchild->v;parent[now->rchild->v] = now->v;layer[now->rchild->v] = layer[now->v]+1;Q.push(now->rchild);}}return;
}Node* create(int inL,int inR,int poL,int poR){if(poL>poR||inL>inR)return NULL;Node* root = new Node;root->v = postSeq[poR];int i;for(i=inL;i<=inR;i++){if(inSeq[i]==root->v){break;}}int leftNum = i - inL;root->lchild = create(inL,i-1,poL,poL+leftNum-1);	root->rchild = create(i+1,inR,poL+leftNum,poR-1);return root;
}int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&postSeq[i]);}for(int i=0;i<n;i++){scanf("%d",&inSeq[i]);}Node* root = create(0,n-1,0,n-1);  BFS(root);int qnum;scanf("%d",&qnum);cin.get();while(qnum--){string str;getline(cin,str);if(str.find("root")!=string::npos){int num;sscanf(str.c_str(),"%d is the root",&num);if(num==root->v)printf("Yes\n");else printf("No\n");}if(str.find("siblings")!=string::npos){int m1,m2;sscanf(str.c_str(),"%d and %d are siblings",&m1,&m2);if(parent[m1]==parent[m2])printf("Yes\n");else printf("No\n");}if(str.find("parent")!=string::npos){int n1,n2;sscanf(str.c_str(),"%d is the parent of %d",&n1,&n2);if(parent[n2]==n1)printf("Yes\n");else printf("No\n");}if(str.find("left")!=string::npos){int n1,n2;sscanf(str.c_str(),"%d is the left child of %d",&n1,&n2);if(lchild[n2]==n1)printf("Yes\n");else printf("No\n");}if(str.find("right")!=string::npos){int n1,n2;sscanf(str.c_str(),"%d is the right child of %d",&n1,&n2);if(rchild[n2]==n1)printf("Yes\n");else printf("No\n");}if(str.find("same")!=string::npos){int n1,n2;sscanf(str.c_str(),"%d and %d are on the same level",&n1,&n2);if(layer[n1]==layer[n2])printf("Yes\n");else printf("No\n");}if(str.find("full")!=string::npos){bool ans = true;for(int i=0;i<n;i++){int n = inSeq[i];if(childNum[n]==1)ans = false;}if(ans)printf("Yes\n");else printf("No\n");}	} return 0;
}

https://www.dkcj.cn/info/17445.html

vs2008 常用快捷键

编辑快捷键 CtrlB,T 切换书签开关 CtrlB,N 移动到下一书签 CtrlB,P 移动到上一书签 CtrlB,C 清除全部标签 CtrlI 渐进式搜索 CtrlShiftI反向渐进式搜索 F12 转到定义 AltF12 查找符号(列出所有查找结果) CtrlF 查找 CtrlH 替换 CtrlShi…

编程日记2024/09/05 21:10:00

我理解的观察者模式

什么是观察者模式？ 当对象间存在一对多关系时,比如，当一个对象被修改时，则会自动通知它的依赖对象。观察者模式也叫做发布订阅模式。观察者模式有什么好处？ 观察者模式中，被观察者发生改变时，会自动通知所…

编程日记2024/09/05 21:00:00

PAT（甲级）2019年春季考试 7-3 Telefraud Detection

1. 这题复杂在诈骗检测算法的理解怎样的一个人会被判定成嫌疑犯呢？ 他打出给别人的累计通话时长的不同的人数大于K 注意：不同和累计怎样的两个人会被判定成同伙呢？ 相互之间有通话记录 2. 同伙的合并我采用的并查集，在设置…

编程日记2024/09/05 20:50:00

Linux基础命令---diffstat

diffstat这个程序读取diff的输出，并显示每个文件的插入、删除和修改的直方图。Diffstat是一个用于检查大型复杂修补程序文件的程序。它从包含diff输出的一个或多个输入文件中读取，生成针对引用的每个文件更改的总行的直方图。如果输入文件名以.bz 2、.gz…

编程日记2024/09/05 20:40:00

两个asp.net发送邮件类

代码 //第一个usingSystem;usingSystem.Text;usingSystem.Net.Mail;namespaceCars.Tootls.Tools{ publicclassEmail { privateEmail() { } ///<summary>///发送邮件 ///</summary>///<param name"Su…

编程日记2024/09/05 20:30:00

symfony2是什么？

首先，symfony2是一个松散的，独立的，有组织严密的php组件的集合，它可以为你解决一些web开发中一般性的问题。其次，基于这些组件，php又可以作为一个独立web框架使用。转载于:https://www.cnblogs.com/ljcph…

编程日记2024/09/05 20:20:00

PAT（甲级）2019年春季考试 7-2 Anniversary

注意点 1. 记录是不是校友，有两种方法 （1）map<string,int> mp mo[guest] 1 判断mp[comer] （2）set<string> st st.insert(guest) st.count(comer) 2. 由于只需要输出年龄最大的&…

编程日记2024/09/05 20:10:00

根据总用量计算每种包装规格的购买量和总价

最近有这么一个需求，就是给出客户需要的总量，然后根据数据库记录的包装规格，计算出客户需要购买的包装规格种类和个数，而且要保证客户的花费最小。示例图片效果示例代码实现如下。欢迎大家一起讨论。代码 using System;using S…

编程日记2024/09/05 20:00:00

5个在线调试代码的网站

对于编程开发的人来说，有个快速测试代码的地方是非常方便重要的，这里，我们收集了5个很好用的在线调试网站。 1.codepad 是一款简单的在线 IDE 编辑器服务，你只需要把代码粘贴进去就可以编译运行了，连工程也不需要新建&…

编程日记2024/09/05 19:50:00

Windows 日志高级筛选实践

背景经常需要查看日志，不仅是用来排错，有些时候我还需要监控系统来抓取特定日志来帮助减少我的工作负担，以及时监控到异常出现，并作出通知及响应，那么从大量日志中快速并精确筛选出想要的日志，并且精确提取…

编程日记2024/09/05 19:40:00

PAT（甲级）2018年秋季考试 7-1 Werewolf - Simple Version

1. 我设置了一个结构体变量存储每个人的指控信息 struct IF{int type 0;int no; }; 这里我发现了一件事，如果结构体只有有参数的构造函数，那么直接声明该结构体类型的数组是不行的。但是好处是数组知道下标可以直接赋值。也就是这样组合最好&#x…

编程日记2024/09/05 19:30:00

appium 启动失败解决方案

本机下载了：AppiumForWindows，启动Appium.exe 的时候，立即提示：应用程序已停止运行！！ 本机环境： WIN 7 64 位，后来查了资料才知道Appium 要求安装.net framework 4.5，本机…

编程日记2024/09/05 19:20:00

Django基础-数据分页

2019独角兽企业重金招聘Python工程师标准>>> pager.py # -*- coding:utf8 -*- """ 引用说明： 数据总个数：total_count 数据总页数：num_pages 每页显示的行数：perPageItemNum【默认显示10行】最多显示页…

编程日记2024/09/05 19:10:00

存货的计划属性设置（ATO模型和PTO模型）

对于原来应用ERP1时已经存在的存货，如果在存货属性中没有进行过设置或者设置不完善，需要进行补充设置。这样的补充设置包括： 自制：具有该属性的存货可由企业生产自制。如工业企业生产的产成品、半成品等存货。具有该属性的存货可用…

编程日记2024/09/05 19:00:00

(C++)判断一个序列是non-increasing/non-decreasing还是两者都不的两个方法

思路：根据前两个值预设类型，再遍历后面的pair，看是否推翻预设 int judgeType(vector<int> vi){//-1 递减 0 啥也不是 1 递增 if(vi.size()1)return 0;//根据前两个元素的大小设置初始类型int type;if(vi[1]>vi[0])type 1;else …

编程日记2024/09/05 18:50:00

public static void down(HttpServletRequest request, HttpServletResponse response) throws Exception { String name"aaa.*";//文件名 String uploadPath UploadFileHelper.getRepositoryPath()"//";//文件来源 String filePath…

编程日记2024/09/05 18:40:00

不要小看字符串

字符串非常非常常见又重要，而且还有那么多名堂在里面字符串: 在标准C中，是没有字符串变量的，但是有字符数组。而且标准C带有的标准库函数：string.h中包含了大量的字符串操作函数，当然如果必要的话，你也可以…

编程日记2024/09/05 18:30:01

零基础学习Python需要注意的几个点，Python培训机构排名

俗话说的好万事开头难，不管你做任何事情，开头的确很较难的，学Python编程也是如此，因此刚开始学Python编程的同学们，就要多借鉴过来人的经验，少走弯路，本文小编就为大家分享几个Python编程小白初…

编程日记2024/09/05 18:20:00

PAT（甲级）2018年冬季考试 7-4 Heap Paths(非递归与递归解法)

非递归解法 1. 前置知识：完全二叉树的属性 1.1 从1开始存储，子节点的下标除以二得到的是父节点的下标 1.2 数组的存放顺序刚好是层序遍历顺序 1.3 从1开始存储，节点的下标i和结点总数n如果满足 i*2>n说明该结点是叶子结点 2. 思路&am…

编程日记2024/09/05 18:10:00

Request Connection: Remote Server @ 192.229.145.200:80

录制Loadrunner脚本时，提示：Request Connection: Remote Server 192.229.145.200:80 NOT INTERCEPTED!(REASON: User requested to IGNORE connection)；解决方法：1. 打开IE里的Internet选项，单击连接选项卡。单击最…

编程日记2024/09/05 18:00:00

抽象工厂与工厂模式例子

NativeFactory。java package com;//定义人有杀日本人和杀美国人两个方法interface NativePerson{ public void killAmeria(); public void killJapan();}//中国人实现了人的接口 class NativeChinese implements NativePerson{ //中国人杀美国人 public void killAmeria() …

编程日记2024/09/05 17:50:00