AKSZ-树图
2024-06-16 16:36:49
发布于:广东
二叉树
对于任意一颗二叉树,如果其叶子结点数量为n0,度为2的结点数为n2,则n0 = n2 + 1
具有n个结点的完全二叉树深度为logn + 1
满n叉树,深度为k
结点的个数 为 (n^k - 1)/ (n-1)
图的度
在无向图中,一个顶点的度数就是与该边相连的顶点的数量
有向图中:入度:指向该顶点的边的数量
出度:从该顶点出发的边的数量
完全二叉树
如果一颗完全二叉树自顶向下,同一层从左到右编号结点
1,2,... n
则
1.若i=1,则为根,无父结点
2.若i>1,则其父结点为floor(i/2)
3.若2i > n ,则i无左孩子,否则其左孩子编号为 2i
4.若2i + 1> n,则i无右孩子,否则其左孩子编号为 2i+1
图的存储
带权图的存储 : 二维数组(两点间无连边用0x3f3f 表示)
先序遍历
二叉树重建
二叉树用中序遍历+任意一种遍历方式可以确定唯一一棵二叉树。
先序+后序不行
根据后序(前序)和中序求另一遍历顺序
#include<bits/stdc++.h>
using namespace std;
int a[200009],b[200009],n,tmp[200009];
void f(int l1,int r1,int l2,int r2){
if(l1 == r1){
cout << a[l1] << " ";
return;
}
// 递归划分
int root = b[r2];
// 中序中找到根的位置
int pos = tmp[root];
cout << root << " ";
if(pos-1 >= l1)
f(l1,pos-1,l2,l2+pos-l1-1);
if(pos + 1 <= r1)
f(pos+1,r1,l2+pos-l1,r2-1);
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<=n;i++){
cin >> b[i];
}
for(int i=1;i<=n;i++){
tmp[a[i]] = i;
}
f(1,n,1,n);
return 0;
}
这里空空如也
有帮助,赞一个