西安网站制作顶尖公,建设假网站,注册企业网站,微信上如何投放广告目录树什么是二叉树二叉树的五种状态满二叉树完全二叉树二叉排序树平衡二叉树二叉树的遍历B3642 二叉树的遍历P1305 新二叉树二叉树的深度P4913 【深基16.例3】二叉树深度相关例题训练#xff1a;二叉树问题树 这是树#xff08;拍摄于郑州轻工业大学#xff0c;第一次郑州轻…
目录树什么是二叉树二叉树的五种状态满二叉树完全二叉树二叉排序树平衡二叉树二叉树的遍历B3642 二叉树的遍历P1305 新二叉树二叉树的深度P4913 【深基16.例3】二叉树深度相关例题训练二叉树问题树 这是树拍摄于郑州轻工业大学第一次郑州轻工业新生赛~ 这是树的一些概念
什么是二叉树 二叉树是n(n0)个节点的有限集合。
1.每个节点最多只有两个子树2.左右子树不能颠倒 二叉树是有序树
二叉树的五种状态 几种特殊的二叉树 满二叉树
高度为h且含有2h2^h2h-1个结点的二叉树 特点
1.只有最后一层有叶子结点2.不存在度为一的点3.按层序从1开始编号结点i的左孩子为2i,右孩子为2i1
完全二叉树
当且仅当其每个结点都与高度为h的满二叉树中编号问为1~n的结点一 一对应时成为完全二叉树。 特点
1.只有最后两层可能有叶子结点。2.最多 只有一个度为1的结点。3.按层序从1开始编号结点i的左孩子为2i,右孩子为2i1
二叉排序树
左子树上所有结点的关键字均小于根节点的关键字 右子树上所有结点的关键字均大于根节点的关键字 左子树和右子树又分别时一颗二叉排序树
平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1 (有更高的搜索效率)
二叉树的遍历
前序遍历 中序遍历 后序遍历 关于遍历二叉树有一个巧妙的方法分享给大家。 以下图为例 以中序遍历左根右 为例 我们可以先遍历最上边的ABC, 并给B和C的子节点留上位置 _ B _ A _ C _ 然后再将B和C的子节点按左根右的顺序填上去 就是这个顺序DBEAFCG 同理你可以练习一下 先序遍历ABDECFG 后序遍历DEBFGCA 有了以上的基础我们拿道题练练手吧 B3642 二叉树的遍历
B3642 二叉树的遍历
题目描述
有一个 n(n≤106)n(n \le 10^6)n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 nnn建立一棵二叉树根节点的编号为 111如果是叶子结点则输入 0 0。
建好树这棵二叉树之后依次求出它的前序、中序、后序列遍历。
输入格式
第一行一个整数 nnn表示结点数。
之后 nnn 行第 iii 行两个整数 lll、rrr分别表示结点 iii 的左右子结点编号。若 l0l0l0 则表示无左子结点r0r0r0 同理。
输出格式
输出三行每行 nnn 个数字用空格隔开。
第一行是这个二叉树的前序遍历。
第二行是这个二叉树的中序遍历。
第三行是这个二叉树的后序遍历。
输入 #1
7
2 7
4 0
0 0
0 3
0 0
0 5
6 0输出 #1
1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1这是一道很模板的二叉树遍历练习题很适合新手宝宝体质按顺序根据前序中序和后续的遍历顺序结合深搜就可以很容易的输出顺序啦~代码注释很详细 AC代码
#includebits/stdc.h
using namespace std;
const int N1e66;
int n,l[N],r[N];//l和r分别存左子节点和右子节点
//前序遍历根左右
void a(int x)//前序遍历访问到第x号点
{if(x0)return ;//题目中说这个结点为0时表示无此结点//然后就是按照前序遍历coutx ;//先输出根a(l[x]);//再输出左子结点a(r[x]);//最后输出右子节点
}
//中序遍历左根右
void b(int x)//中序遍历访问到第x号点
{if(x0)return ;//中序遍历 b(l[x]);//先输出左子结点coutx ;//再输出根b(r[x]);//最后输出右子节点
}
//后序遍历左右根
void c(int x)//后序遍历访问到第x号点
{if(x0)return ;//后序遍历顺序 c(l[x]);//先输出左子结点c(r[x]);//再输出右子节点 coutx ;//最后输出根
}
int main()
{cinn;for(int i1;in;i)cinl[i]r[i];//输入对应位置的左右节点 //前序遍历根左右 a(1);//根节点从1开始遍历coutendl;//前序遍历完后要输出换行//中序遍历左根右b(1);//根节点也是从1开始中序遍历coutendl;//后序遍历左右根c(1);coutendl; return 0;
} 再来一道例题练练手吧 P1305 新二叉树
P1305 新二叉树
题目描述
输入一串二叉树输出其前序遍历。
输入格式
第一行为二叉树的节点数 nnn。(1≤n≤261 \leq n \leq 261≤n≤26)
后面 nnn 行每一个字母为节点后两个字母分别为其左右儿子。特别地数据保证第一行读入的节点必为根节点。
空节点用 * 表示
输出格式
二叉树的前序遍历。
输入 #1
6
abc
bdi
cj*
d**
i**
j**输出 #1
abdicj一道很基础的二叉树题可以通过结构体将这个二叉树建立起来虽然题目中给的字符但同样可以存储在结构体数组中因为字符ACS码最大不超过128所以数组只需开150就足够然后可以利用深搜将第一个节点传入dfs依次搜索当子节点不为 * 时才继续往下搜。 AC代码
#includebits/stdc.h
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pairint,int
#define fi first
#define se second
#define endl \n
const int N1e66;
struct node//简单的建树
{char l,r;
}p[150];
int n;
void dfs(char bg)
{coutbg;if(p[bg].l !*) dfs(p[bg].l);//如果不为空节点就接着往下搜 if(p[bg].r !*) dfs(p[bg].r);
}
void solve()
{cinn;char a,x,y,bg;cinaxy;bga;//作为初始深搜的点 p[a].l x,p[a].r y;//左右子数 n-1;while(n--){cinaxy;p[a].l x,p[a].r y;}dfs(bg);
}
signed main()
{IOS;int _1;
// cin_;while(_--)solve();return 0;
} 二叉树的深度
二叉树深度简而言之就是这个二叉树最多有几层 比如这个二叉树它的深度就是3 我们直接上例题感受一下吧 P4913 【深基16.例3】二叉树深度
题目描述
有一个 n(n≤106)n(n \le 10^6)n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 nnn建立一棵二叉树根节点的编号为 111如果是叶子结点则输入 0 0。
建好这棵二叉树之后请求出它的深度。二叉树的深度是指从根节点到叶子结点时最多经过了几层。
输入格式
第一行一个整数 nnn表示结点数。
之后 nnn 行第 iii 行两个整数 lll、rrr分别表示结点 iii 的左右子结点编号。若 l0l0l0 则表示无左子结点r0r0r0 同理。
输出格式
一个整数表示最大结点深度。
输入 #1
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0输出 #1
4思路分析 我们可以先利用结构体读入这个二叉树 拥有左子节点和右子节点两个参数的结构体开n范围的结构体数组 搜索dfs) 状态当前走到什么编号的节点以及当前的深度终止条件走到0号节点更新最大深度)走到哪里去当前所在编号的节点的左右子节点 输出最大深度 AC代码
#includebits/stdc.h
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pairint,int
#define fi first
#define se second
#define endl \n
const int N1e66;
struct node//建树
{int l,r;
}p[N];
int n,ansINT_MIN;//ans用来记录树的最大深度
void dfs(int x,int h)
{//终止条件子节点为0时 ansmax(ans,h);//更新最大值 //走到哪里去if(p[x].l)//如果左子节点不为0 dfs(p[x].l,h1);if(p[x].r)//如果右子节点不为0 dfs(p[x].r,h1);
}
void solve()
{cinn;for(int i1;in;i)cinp[i].lp[i].r;dfs(1,1);//传入最初所在位置和最初深度coutans;
}
signed main()
{IOS;int _1;
// cin_;while(_--)solve();return 0;
} 相关例题训练
二叉树问题
P3884 [JLOI2009] 二叉树问题 题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为
深度444宽度444结点 8 和 6 之间的距离888结点 7 和 6 之间的距离333
其中宽度表示二叉树上同一层最多的结点个数节点 u,vu, vu,v 之间的距离表示从 uuu 到 vvv 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。 给定一颗以 1 号结点为根的二叉树请求出其深度、宽度和两个指定节点 x,yx, yx,y 之间的距离。
输入格式
第一行是一个整数表示树的结点个数 nnn。 接下来 n−1n - 1n−1 行每行两个整数 u,vu, vu,v表示树上存在一条连接 u,vu, vu,v 的边。 最后一行有两个整数 x,yx, yx,y表示求 x,yx, yx,y 之间的距离。
输出格式
输出三行每行一个整数依次表示二叉树的深度、宽度和 x,yx, yx,y 之间的距离。
输入 #1
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6输出 #1
4
4
8说明/提示
对于全部的测试点保证 1≤u,v,x,y≤n≤1001 \leq u, v, x, y \leq n \leq 1001≤u,v,x,y≤n≤100且给出的是一棵树。保证 uuu 是 vvv 的父结点。 求深度 1.构建树用结构体更方便2.dfs对每个节点深度赋值3.找到所有节点深度最大值 求宽度 1.统计每一层的宽度2.求宽度最大值 求距离 BFS AC代码
#includebits/stdc.h
using namespace std;
struct node//建树
{int l,r,f,d;//分别代表左子节点、右子节点、父节点和当前节点深度
}ns[105];
struct node2//便于查找距离
{int pos,step;
};
int dp0,wd,wid[105],st[105];//分别表示当前最大深度、宽度宽度数组和状态数组
void dfs(int p)
{if(st[p])return ;//如果已经被访问过return st[p]1;//标记为1 int lens[p].l ,rins[p].r ,dens[p].d;//左子节点右子节点深度赋值 dpmax(dp,de);//更新最大深度 wid[de];//记录宽度 if(le)//如果有左子节点 {ns[le].dde1;//深度加1 dfs(le);//接着向下搜 }if(ri)//如果有右子节点 {ns[ri].d de1;dfs(ri);}
}
int main()
{int n,u,v,x,y;cinn;for(int i1;in;i)//n-1条边 {cinuv;if(!ns[u].l) ns[u].l v;//如果没有左子节点存入左子节点 else ns[u].r v;//否则存入右子节点 ns[v].fu;//记得更新父节点 }cinxy;//输入要查找距离的两个点 ns[1].d 1; //第一个节点即初始深度为1 dfs(1);//传入当前位置节点 for(int i1;in;i)//循环遍历找出最大宽度 wdmax(wd,wid[i]);coutdpendlwdendl;//输出最大深度和最大宽度 memset(st,0,sizeof(st));//将状态数组重置为0 node2 tn{x,0};//将初始点和距离值传入 st[x]1;//状态改变表示已被访问过 queuenode2q;//建立结构体状态数组 q.push(tn);//将初始状态传进去 while(!q.empty())//当队列不空时 {tnq.front();//取队首元素 q.pop();//队首弹出 if(tn.posy)//当所查找的值到达y时 {couttn.step;//输出距离 break;//查找结束 }int lens[tn.pos].l;int rins[tn.pos].r;int fans[tn.pos].f;int steptn.step ;if(le!st[le])//如果左子节点不空并且没被访问过 {st[le]1;//更新状态数组 q.push({le,step1});//将更新后的位置和距离压入队列 }if(ri!st[ri])//以下同理 {st[ri]1;q.push({ri,step1});}if(fa!st[fa]){st[fa]1;q.push({fa,step2});//因为到父节点是向上走所以每次更新两步 }} return 0;
}
