Note / 二叉树 08.18
2023-08-18 16:30:38
发布于：广东
3阅读
0回复
0点赞
X02 C3 广深
1,树的深度：树中节点的最大层数即树的高度或深度
2,节点的度，一个节点拥有的子树数
3,叶子节点:度为0的节点
满二叉树：所有层的节点数都达到最大
完全二叉树：除最后一层不满外，其余层的都达到该层的最大节点数，最后如果不满，该层所有节点都全部靠左排
二叉树三种遍历方式：
前序遍历：先遍历根节点，再遍历左节点，最后遍历右节点
中序遍历：先遍历左节点，再遍历根节点，最后遍历右节点
后序遍历：先遍历左节点，再遍历右节点，最后遍历根节点
1.n个节点的二叉树一共有(2n)!/ (n!* (n+1)!) 种
2.n层二叉树的第n层最多为2^(n-1)个
3.二叉树节点计算公式N=n0+n1+n2,度为0的叶子节点比度为2的节点数多一个。N=1n1+2n2+1
4.对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1
5.具有n个节点的完全二叉树的深度为log2(n)+1
下午写的连通图+广搜的T2091 题解带注释详解
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> g[200005];
int n,m,u,v,flag,vis[200005];
void bfs(){
queue<int> que; //创建bfs队列
que.push(u); //添加起点
while (!que.empty()){ //如队列是空的 代表已经找到 则停止循环
int k=que.front(); //如不是空的 拿一个数据做处理
que.pop(); // 处理了之后删除他
for(int i=0;i<g[k].size();++i){ //遍历这个数据能去到的所有点
if(vis[g[k][i]]!=0) continue; //如果这个点被标记过 就跳过
if(g[k][i] == v){ //如果 这个点是终点 就找到了 随后return
flag=1; //标记flag为1 方便输出
return;
}
que.push(g[k][i]); //没找到的话就存入队列
vis[g[k][i]] = 1; //标记走过
}
}
}
int main(){
cin>>n>>m>>u>>v; //西印
for(int i=0;i<m;++i){
int a,b;
cin>>a>>b;
g[a].push_back(b);
}
bfs();
if(flag) cout<<"Yes"; //西奥特
else cout<<"No";
return 0;
}
有帮助，赞一个