A.常用知识点

1. BST的中序遍历序列是递增序列，排个序即可

1. 二叉树的建树

int v[N],l[N],r[N],idx=1;
//v,l,r中i表示地址

//更新
void newnode(int x){
    v[idx]=x;
    l[idx]=r[idx]=0;
    idx++;
}

2. 多叉树的建树

直接使用邻接矩阵表示就好

int h[N],e[N],ne[N],idx=1;
int v[N];
//e,ne,w中的i为地址idx
//h,v中的i为结点序号0-n,若有大数字，可存在v中

void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

B.通过2个序列建树问题

1. 请由前序和中序建立树，得到后序序列

1. 本质上dfs，调整左-根-右的顺序，即可得到另一个序列

int preorder[N];
int inorder[N];
vector<int>postorder;
//会有重复元素，不能用哈希表存储中序位置，只能从前往后找 
bool build(int pl,int pr,int il,int ir){
    if(il>ir){
        //找得完,则该树存在 
        return true;
    }
    int root=preorder[pl];
    //前序遍历第一个元素是根节点
    int k;
    for(k=il;k<=ir;k++){
        if(inorder[k]==root){
            //找到了根节点在中序的位置 
            break;
        }
    } 
    if(k>ir){
        //找不到root在中序的位置
        return false; 
    }
    if(build(pl+1,pl+k-il,il,k-1)==0)   return false;
    //左子树建不了树
    //len=k-1-il+1=k-il
    if(build(pl+k-il+1,pr,k+1,ir)==0)   return false;
    //右子树建不了树

    //dfs，左-右-根，后序遍历
    postorder.push_back(root); 
} 
int main(){
    build(0,n-1,0,n-1);
    for(auto &i:postorder){
        cout<<i<<" ";
    }
} 

C. BST问题

1. 给一个序列逐个插入，构造二叉搜索树

 int l[N],r[N],v[N],idx=0;
//表示地址idx所对应的左右子树的地址以及值

//二叉搜索树的插入代码 
void insert(int &u,int w){
    //u表示结点所在地址,因为要改变根节点的地址，因此要用引用
    //w表示地址为u所对应的结点值
    if(u==0){
        //为空，则新建一个结点 
        u=++idx;
        v[u]=w;
        return;
    } 
    if(w<=v[u]) insert(l[u],w);
    //小则插到左子树
    if(w>v[u])  insert(r[u],w);
    //大则插到右子树
} 
int main(){
    cin>>n;
    int root=0;
    while(n--){
        int x;
        cin>>x;
        insert(root,x);
    }
} 

D. 树的搜索问题

获取树的每一层的结点数

1. 采用dfs递归求取即可(前，中，后序都可)

int cnt[N];

void dfs(int u,int depth){
    if(u==0)    return;
    cnt[depth]++;
    //计算每层的节点数 

    dfs(l[u],depth+1);
    dfs(r[u],depth+1);
}

DFS进行层序遍历

1. 思路同上
2. dfs前中后序遍历都可以，因为左右顺序固定不变

vector<int>ans[N];//存储每一层结点的值
int max_depth=0;//最大深度

void dfs(int u,int depth){
    if(u==0)    return;
    max_depth=max(max_depth,depth);//更新最大深度

    ans[depth].push_back(u);//存储当前层的节点
    if(l[u]!=0) dfs(l[u],depth+1);//访问左子树
    if(r[u]!=0) dfs(r[u],depth+1);//访问右子树
}

int main(){
    dfs(root,1);//从根节点开始访问，当前层数为1
    for(int i=1;i<=max_depth;i++){
        for(auto j:ans[i]){
            cout<<j<<" ";
        }
    }
}