二叉树部分的题目

2024-09-04 05:32
文章标签 二叉树 题目 部分

本文主要是介绍二叉树部分的题目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉树的存储

P4715 【深基16.例1】淘汰赛

#include <bits/stdc++.h>
using namespace std;
int n, id, value[260], win[260], total, ans;
void dfs(int cur){if(cur>total-1){return;}int leftid=2*cur;int rightid=2*cur+1;dfs(leftid);dfs(rightid);if(value[leftid]>value[rightid]){value[cur]=value[leftid];win[cur]=win[leftid];}else{value[cur]=value[rightid];win[cur]=win[rightid];}
}
int main()
{scanf("%d", &n);total=1<<n;/*12            34      5     6      78   9  10 11 12 13  14  15  */for(int i=0; i<total; ++i){id=total+i;scanf("%d", &value[id]);win[id]=i+1;}dfs(1);if(value[2]>value[3]){ans=win[3];}else{ans=win[2];}printf("%d", ans);return 0;
}

P4913 【深基16.例3】二叉树深度

#include<bits/stdc++.h>
using namespace std;
int n, a[1000010][3], l, r, ans;
void dfs(int curdeep, int x)
{if(a[x][1]==0 && a[x][2]==0){   //无左子树和右子树ans=max(ans, curdeep);return;}if(a[x][1]!=0){     //有左子树dfs(curdeep+1, a[x][1]);}if(a[x][2]!=0){     //有右子树dfs(curdeep+1, a[x][2]);}
}
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d %d", &l, &r);a[i][1]=l;a[i][2]=r;}dfs(1, 1);    printf("%d", ans);return 0;
}

P5076 【深基16.例7】普通二叉树(简化版)

#include <bits/stdc++.h>
using namespace std;
int q, x, opt, n, site, a[10001], b[10001];
int main()
{scanf("%d", &q);while(q--){scanf("%d", &opt);scanf("%d", &x);if(opt==1){	//查询x的排名, 坑点:不用管x在不在里面, 只用找出有多少个比x小即可 int cnt=0;for(int i=1; i<=n; ++i){if(a[i]<x){cnt++;}} printf("%d\n", cnt+1);}else if(opt==2){	//查询排名为x的数, 坑点:不用去重 printf("%d\n", a[x]);}else if(opt==3){	//求x的前驱,未找到前驱则输出-2147483647//坑点:不用管x在不在里面, 只用找到比x小的数里的最大值 int pre=-2147483647; for(int i=1; i<=n; ++i){if(a[i]<x){pre=max(pre, a[i]);}else{break;}}printf("%d\n", pre);} else if(opt==4){	//求x的后继,若未找到后继则输出 2147483647//坑点:不用管x在不在里面, 只用找到比x大的数里的最小值bool flag=false; for(int i=1; i<=n; ++i){if(a[i]>x){flag=true;printf("%d\n", a[i]);break;}}if(!flag){	//没有后继 printf("2147483647\n"); }}else if(opt==5){	//插入一个数 x//找到在哪个位置插入, 然后插入if(n==0){	//插入第一个数时 n++;a[n]=x;}else if(x<=a[1]){	//在开头插入 for(int i=n; i>=1; --i){a[i+1]=a[i];}a[1]=x;n++;} else if(x>=a[n]){	//在末尾插入 n++;a[n]=x;} else{	//在中间插入 for(int i=1; i<=n-1; ++i){if(x>=a[i] && x<=a[i+1]){site=i+1; } } for(int i=n; i>=site; --i){a[i+1]=a[i];}a[site]=x;n++;} }}return 0;
} 

二叉树的三种遍历方法

P1030 [NOIP2001 普及组] 求先序排列

#include <bits/stdc++.h>
using namespace std;
string in_order, post_order;
int len;
//中序 从l1到r1,后序从l2到r2 
void dfs(int l1, int r1, int l2, int r2)
{int flag;//剪枝,已经没有节点了,树为空 if(l1>r1 || l2>r2)	return;	//后序遍历最后一个肯定是根节点 char root=post_order[r2];	//输出根结点 cout << root;//在中根遍历序列中找到根结点所在的位置,即可将结点分为左子树和右子树 for(int i=l1; i<=r1; ++i){if(in_order[i]==root){	//如果等于根 //flag记录的是中序遍历序列中,根结点的位置//在中根序列中,l1到flag-1的节点都属于左子树, //flag+1到r1的节点都属于右子树 flag=i; 	 break; }}//现在问题的关键是如何找出新的左子树的后序遍历序列、新的右子树的后续遍历序列//原来的后续遍历序列前面部分是左子树的后续序列,紧接着是右子树的后续序列,最后是跟结点//所以需要知道左子树有多少个结点。int left_node=flag-l1;//左子树有left_node个结点,则在后续遍历序列中,左子树的范围是从l2到l2+left_node-1 //紧接着就是右子树,则在后续遍历序列中,右子树的范围是从l2+left_node到r2-1 if(l1<flag)		//如果左边节点小于根结点的编号,说明有左子树,递归左子树 dfs(l1, flag-1, l2, l2+left_node-1);	if(flag<r1)		//如果右边节点大于根结点的编号,说明有右子树,递归右子树 dfs(flag+1, r1, l2+left_node, r2-1);	 
}
int main()
{cin >> in_order >> post_order;len=in_order.length();	//获取结点的数量 //中序从0到len-1, 后序从0到len-1 dfs(0, len-1, 0, len-1);return 0;
}

P1827 [USACO3.4]美国血统 American Heritage

先建树、后遍历

#include <bits/stdc++.h>
using namespace std;
char first;
int length;
string preorder, inorder;
//a[1]['C']='B', 表示'C'的左儿子是'B'
//a[2]['C']='G', 表示'C'的右儿子是'G'
map<char, char> a[3];	 
//s1 e1表示中序遍历序列的起终点下标
//s2 e2表示前序遍历序列的起终点下标 
//对树的中序遍历、先序遍历进行递归, 找出每个结点的左右儿子
void dfs(int s1, int e1, int s2, int e2)
{int rootid, leftnum=0;if(s1==e1 || s2==e2){	//*表示为空 a[1][inorder[s1]]=a[2][inorder[s1]]='*';a[1][preorder[s2]]=a[2][preorder[s2]]='*';return;}//找到根 char root=preorder[s2]; //在中序遍历中找到根的下标for(int i=s1; i<=e1; ++i){leftnum++;	//左子树的结点数(包含root) if(inorder[i]==root){rootid=i;break;}} //root根有左儿子 if(rootid>s1){//记录左儿子 a[1][root]=preorder[s2+1]; //对左子树的中序遍历、先序遍历进行递归, 找出每个结点的左右儿子dfs(s1, rootid-1, s2+1, s2+leftnum-1); }else{a[1][root]='*';}//root根有右儿子 if(rootid<e1){//记录右儿子 a[2][root]=preorder[s2+leftnum];//对右子树的中序遍历、先序遍历进行递归, 找出每个结点的左右儿子 dfs(rootid+1, e1, s2+leftnum, e2);} else{a[2][root]='*';}
}
void postorder(char cur)
{//没有左子树 if(a[1][cur]=='*'){		//*表示为空 //没有右子树 if(a[2][cur]=='*'){printf("%c", cur);}else{	//有右子树 //对右子树进行后序遍历 postorder(a[2][cur]);printf("%c", cur);	//输出根节点 } } else{	//有左子树 //对左子树进行后序遍历 postorder(a[1][cur]);//没有右子树 if(a[2][cur]=='*'){printf("%c", cur);	//输出根节点 }else{	//有右子树 //对右子树进行后序遍历 postorder(a[2][cur]);printf("%c", cur);	//输出根节点 } }
}
int main()
{cin >> inorder >> preorder;first=preorder[0];	//二叉树的根节点 length=inorder.length();dfs(0, length-1, 0, length-1);	//注意length-1 postorder(first);	//递归求后序遍历 return 0;
}

P1364 医院设置

#include <bits/stdc++.h>
using namespace std;
int n, dis[110], cur, ans=2e9, u, v, w[110], a[110][4];
bool vis[110];
//id结点到医院的距离为x 
void dfs(int id, int x)
{//遍历id结点的左儿子、右儿子、父节点 for(int i=1; i<=3; ++i){//如果有, 并且没被遍历过 if(a[id][i]!=0 && !vis[a[id][i]]){//标记为遍历过 vis[a[id][i]]=true;//更新最短距离 dis[a[id][i]]=x+1;//深搜 dfs(a[id][i], x+1);}} 
} 
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d %d %d", &w[i], &u, &v);a[i][1]=u;	//i的左儿子 a[i][2]=v;	//i的右儿子a[u][3]=a[v][3]=i;	//u、v的父节点 }//枚举医院的所有可能 for(int i=1; i<=n; ++i){cur=0;memset(dis, 0, sizeof(dis));memset(vis, 0, sizeof(vis));//从医院出发, 去找其他n-1个点 vis[i]=true;dfs(i, 0);for(int j=1; j<=n; ++j){cur+=w[j]*dis[j];}ans=min(ans, cur);}printf("%d", ans);return 0;
}

P3884 [JLOI2009]二叉树问题

#include <bits/stdc++.h>
using namespace std;
int n, a[110][4], u, v, height=1, width, dis, num[110];
bool vis[110];
//找深度和宽度 
void dfsheight(int id, int x)
{for(int i=1; i<=2; ++i){if(a[id][i]!=0){	//有儿子 height=max(height, x+1);num[x+1]++;		//第x+1层节点数加一 dfsheight(a[id][i], x+1); }}
} 
//找距离 
void dfsdis(int id, int x)
{if(id==v){dis=x;printf("%d\n%d\n%d", height, width, dis);exit(0);} for(int i=1; i<=3; ++i){if(a[id][i]!=0 && !vis[a[id][i]]){	//有儿子, 并且没访问过 vis[a[id][i]]=true;if(i==3){	//向上 dfsdis(a[id][i], x+2); }else{	//向下 dfsdis(a[id][i], x+1); } }}
} 
int main()
{scanf("%d", &n);for(int i=1; i<n; ++i){scanf("%d %d", &u, &v);if(a[u][1]==0){a[u][1]=v;	//u的左儿子是v }else{a[u][2]=v;	//u的右儿子是v}a[v][3]=u;	//v的父节点是u }scanf("%d %d", &u, &v);num[1]=1;dfsheight(1, 1);//找宽度 for(int i=1; i<=height; ++i){width=max(width, num[i]);}//找距离vis[u]=true;	//标记 dfsdis(u, 0); return 0;
} 

P1229 遍历问题

#include <bits/stdc++.h>
using namespace std;
string s1, s2;
int length;
long long ans=1;
int main()
{cin >> s1 >> s2;reverse(s2.begin(), s2.end());length=s1.length();for(int i=0; i<length-1; ++i){for(int j=j=0; j<length-1; ++j){if(s1[i]==s2[j] && s1[i+1]==s2[j+1]){ans*=2;}}}printf("%lld", ans);return 0;
}

这篇关于二叉树部分的题目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1135128

相关文章

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

笔记整理—内核!启动!—kernel部分(2)从汇编阶段到start_kernel

kernel起始与ENTRY(stext),和uboot一样,都是从汇编阶段开始的,因为对于kernel而言,还没进行栈的维护,所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用,前面关于uboot的文章中有提到过(eg:zImage)。uboot启动是无条件的,只要代码的位置对,上电就工作,kern

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

项目实战系列三: 家居购项目 第四部分

购物车 🌳购物车🍆显示购物车🍆更改商品数量🍆清空购物车&&删除商品 🌳生成订单 🌳购物车 需求分析 1.会员登陆后, 可以添加家居到购物车 2.完成购物车的设计和实现 3.每添加一个家居,购物车的数量+1, 并显示 程序框架图 1.新建src/com/zzw/furns/entity/CartItem.java, CartItem-家居项模型 /***

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

关于断言的部分用法

1、带变量的断言  systemVerilog assertion 中variable delay的使用,##[variable],带变量的延时(可变延时)_assertion中的延时-CSDN博客 2、until 的使用 systemVerilog assertion 中until的使用_verilog until-CSDN博客 3、throughout的使用   常用于断言和假设中的