1. 基本
二叉树的定义
int v[N],l[N],r[N],idx=1;
//v,l,r的下标都表示地址idx
//新建一个结点
int newnode(int x){
v[idx]=x;/赋值
return idx++;//返回该结点的地址
}
2. 建树
通过中序遍历和后序遍历建树
int build(int il,int ir,int pl,int pr){
if(il>ir) return 0;//返回空指针
int root=post[pr];//1. 找到根节点的值
int p=newnode(root);//2. 新建立一个结点
int k;
for(k=il;k<=ir;k++){//3. 找到根节点在中序遍历中的位置
if(in[k]==root){
break;
}
}
l[p]=build(il,k-1,pl,pl+k-il-1);//4. 左儿子赋值
r[p]=build(k+1,ir,pl+k-il,pr-1);//5. 右儿子赋值
return p; //6. 全部都执行完后,返回该结点的地址
}
建立二叉搜索树
#include<bits/stdc++.h>
using namespace std;
const int N=1e2,INF=1e9;
int n;
int post[N],in[N];
unordered_map<int,int>ump;//val->id
int v[N],l[N],r[N],idx=1;
int newnode(int x){
v[idx]=x;
return idx++;
}
void build(int &u,int x){
if(u==0){
int p=newnode(x);
u=p;
return;
}
if(x<=v[u]){
build(l[u],x);
}else{
build(r[u],x);
}
}
void dfs(int u){
if(u==0) return;
dfs(l[u]);
cout<<v[u]<<" ";
dfs(r[u]);
}
int main(){
cin>>n;
int root=0;
while(n--){
int x;
cin>>x;
build(root,x);
}
dfs(root);
}
3. 遍历
注意二叉树的遍历都不需要st数组
层序遍历
void bfs(int u){
queue<int>q;
q.push(u);
while(q.size()){
auto t=q.front();
q.pop();
cout<<v[t]<<" ";
if(l[t]!=0) q.push(l[t]);
if(r[t]!=0) q.push(r[t]);
}
}
前中后序遍历
void dfs(int u){
if(u==0) return;
dfs(l[u]);
cout<<v[u]<<" ";
dfs(r[u]);
}
4. 其他
保存每一层的结点
vector<int>layer[N];
int max_depth=0;
void dfs(int u,int depth){
if(u==0) return;
layer[depth].push_back(v[u]);
max_depth=max(depth,max_depth);
dfs(l[u],depth+1);
dfs(r[u],depth+1);
}