AI 助理
备案控制台
开发者社区 云计算 文章 正文

ACM模板——树的创建（中 + 先、中 + 后、先 + 后）+ 树的遍历（先序、中序、中倒序、后序、层序）+ 求树高

2022-05-17 137
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
传统型负载均衡 CLB，每月750个小时 15LCU
网络型负载均衡 NLB，每月750个小时 15LCU
应用型负载均衡 ALB，每月750个小时 15LCU
简介： ACM模板——树的创建（中 + 先、中 + 后、先 + 后）+ 树的遍历（先序、中序、中倒序、后序、层序）+ 求树高

注释版：

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
using namespace std;
typedef long long ll;
const int maxn=50;
int mid[maxn],po[maxn],pr[maxn];
int first;
struct node
{
    int l,r;
}T[maxn];
// 中序+先序=>二叉树
int mid_pr_build(int la,int ra,int lb,int rb) // la,ra：表示中序遍历  lb,rb：表示先序遍历
{
    // 这里不能等于，因为假设：len==1，则la==ra，直接返回，但是实际上是有一个 rt 的，却没被建立
    if(la>ra) return 0; 
    int rt=pr[lb]; // 因为先序遍历第一个是根节点
    int p1=la,p2;
    while(mid[p1]!=rt) p1++; // 在中序遍历中找到根节点
    p2=p1-la;
    T[rt].l=mid_pr_build(la,p1-1,lb+1,lb+p2); // 左子树（锁定左子树范围的下标）
    T[rt].r=mid_pr_build(p1+1,ra,lb+p2+1,rb); // 右子树（锁定右子树范围的下标）
    return rt;
}
// 中序+后序=>二叉树
int mid_po_build(int la,int ra,int lb,int rb) // la,ra：表示中序遍历  lb,rb：表示后序遍历
{
    if(la>ra) return 0;
    int rt=po[rb]; // 因为后序遍历最后一个是根节点
    int p1=la,p2;
    while(mid[p1]!=rt) p1++; // 在中序遍历中找到根节点
    p2=p1-la;
    T[rt].l=mid_po_build(la,p1-1,lb,lb+p2-1); // 左子树（锁定左子树范围的下标）
    T[rt].r=mid_po_build(p1+1,ra,lb+p2,rb-1); // 右子树（锁定右子树范围的下标）
    return rt;
}
// 求树高
int getHeight(int rt)
{
    if(rt==0) return 0;
    return 1+max(getHeight(T[rt].l),getHeight(T[rt].r));
}
// 层序遍历
void bfs(int rt)
{
    queue<int> q;
    vector<int> v;
    q.push(rt);
    while(!q.empty())
    {
        int w=q.front();
        q.pop();
        v.push_back(w);
        if(T[w].l!=0) q.push(T[w].l);
        if(T[w].r!=0) q.push(T[w].r);
    }
    int len=v.size();
    for(int i=0;i<len;i++)
        printf("%d%c",v[i],i==len-1?'\n':' '); // 推荐这种写法，简洁
}
// 先序遍历
void preT(int rt)
{
    if(rt==0) return;
    printf(first?first=0,"%d":" %d",rt);
    preT(T[rt].l);
    preT(T[rt].r);
}
// 中序遍历
void midT(int rt)
{
    if(rt==0) return;
    midT(T[rt].l);
    printf(first?first=0,"%d":" %d",rt);
    midT(T[rt].r);
}
// 中倒序遍历
void reMidT(int rt)
{
    if(rt==0) return;
    midT(T[rt].r);
    printf(first?first=0,"%d":" %d",rt);
    midT(T[rt].l);
}
// 后序遍历
void postT(int rt)
{
    if(rt==0) return;
    postT(T[rt].l);
    postT(T[rt].r);
    printf(first?first=0,"%d":" %d",rt);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        first=1;
        for(int i=0;i<n;i++) scanf("%d",&po[i]); // 后序结点
//        for(int i=0;i<n;i++) scanf("%d",&pr[i]); // 先序结点
        for(int i=0;i<n;i++) scanf("%d",&mid[i]); // 中序结点
        int rt=mid_po_build(0,n-1,0,n-1); // 中+后，返回根节点
//        int rt=mid_pr_build(0,n-1,0,n-1); // 中+先，返回根节点
        bfs(rt); // 层序遍历
//        preT(rt); // 先序遍历
//        puts("");
//        postT(rt); // 后序遍历
//        puts("");
//        midT(rt); // 中序遍历
//        puts("");
    }
    return 0;
}

简化版（Val As Index，若数据不在1~N内，则可能越界）：

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
using namespace std;
typedef long long ll;
const int maxn=50;
int mid[maxn],po[maxn],pr[maxn];
int first;
struct node
{
    int l,r;
}T[maxn];
int mid_pr_build(int la,int ra,int lb,int rb)
{
    if(la>ra) return 0;
    int rt=pr[lb];
    int p1=la,p2;
    while(mid[p1]!=rt) p1++;
    p2=p1-la;
    T[rt].l=mid_pr_build(la,p1-1,lb+1,lb+p2);
    T[rt].r=mid_pr_build(p1+1,ra,lb+p2+1,rb);
    return rt;
}
int mid_po_build(int la,int ra,int lb,int rb)
{
    if(la>ra) return 0;
    int rt=po[rb];
    int p1=la,p2;
    while(mid[p1]!=rt) p1++;
    p2=p1-la;
    T[rt].l=mid_po_build(la,p1-1,lb,lb+p2-1);
    T[rt].r=mid_po_build(p1+1,ra,lb+p2,rb-1);
    return rt;
}
int getHeight(int rt)
{
    if(rt==0) return 0;
    return 1+max(getHeight(T[rt].l),getHeight(T[rt].r));
}
void bfs(int rt)
{
    queue<int> q;
    vector<int> v;
    q.push(rt);
    while(!q.empty())
    {
        int w=q.front();
        q.pop();
        v.push_back(w);
        if(T[w].l!=0) q.push(T[w].l);
        if(T[w].r!=0) q.push(T[w].r);
    }
    int len=v.size();
    for(int i=0;i<len;i++)
        printf("%d%c",v[i],i==len-1?'\n':' ');
}
void preT(int rt)
{
    if(rt==0) return;
    printf(first?first=0,"%d":" %d",rt);
    preT(T[rt].l);
    preT(T[rt].r);
}
void midT(int rt)
{
    if(rt==0) return;
    midT(T[rt].l);
    printf(first?first=0,"%d":" %d",rt);
    midT(T[rt].r);
}
void reMidT(int rt)
{
    if(rt==0) return;
    midT(T[rt].r);
    printf(first?first=0,"%d":" %d",rt);
    midT(T[rt].l);
}
void postT(int rt)
{
    if(rt==0) return;
    postT(T[rt].l);
    postT(T[rt].r);
    printf(first?first=0,"%d":" %d",rt);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        first=1;
        for(int i=0;i<n;i++) scanf("%d",&po[i]);
//        for(int i=0;i<n;i++) scanf("%d",&pr[i]);
        for(int i=0;i<n;i++) scanf("%d",&mid[i]);
        int rt=mid_po_build(0,n-1,0,n-1);
//        int rt=mid_pr_build(0,n-1,0,n-1);
        bfs(rt);
//        preT(rt);
//        postT(rt);
//        midT(rt);
    }
    return 0;
}

简化版（Val Not As Index，可以存任意的 Val）：

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a)
#define ssclr(ss) ss.clear(), ss.str("")
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
const int maxn=5e4+1000;
int f;
int pre[maxn], in[maxn];
struct node
{
    int l,r,d;
}T[maxn];
int create(int l1,int r1,int l2,int r2) // in pre
{
    if(l2>r2) return -1;
    int rt=l2;
    int p1=l1,p2;
    while(in[p1]!=pre[rt]) p1++;
    p2=p1-l1;
    T[rt].d=pre[rt];
    T[rt].l=create(l1,p1-1,l2+1,l2+p2);
    T[rt].r=create(p1+1,r1,l2+p2+1,r2);
    return rt;
}
void postT(int rt)
{
    if(rt==-1 || !f) return;
    postT(T[rt].l);
    postT(T[rt].r);
    if(f) f=0, printf("%d\n",T[rt].d);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&pre[i]);
    for(int i=0;i<n;i++) scanf("%d",&in[i]);
    int rt=create(0,n-1,0,n-1);
    f=1, postT(rt);
    return 0;
}


文章标签：
负载均衡
相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改，快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡（Server Load Balancer）是对多台云服务器进行流量分发的负载均衡服务，可以通过流量分发扩展应用系统对外的服务能力，通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
Lux_Sun
目录
相关文章
java冯坚持
|
2月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
31 0
sky_qiyi
|
6月前
|
算法
数据结构和算法学习记录——层序遍历（层次遍历）、二叉树遍历的应用（输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树）
数据结构和算法学习记录——层序遍历（层次遍历）、二叉树遍历的应用（输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树）
sky_qiyi
61 0
ForcibleBugMaker
|
7月前
|
机器学习/深度学习 C++
初阶数据结构之---二叉树链式结构（二叉树的构建，二叉树的前序，中序，后序和层序遍历，计算二叉树结点个数，第k层结点个数，叶子结点个数，判断是否为完全二叉树）
初阶数据结构之---二叉树链式结构（二叉树的构建，二叉树的前序，中序，后序和层序遍历，计算二叉树结点个数，第k层结点个数，叶子结点个数，判断是否为完全二叉树）
ForcibleBugMaker
62 0
得过且过的勇者y
|
7月前
LeetCode刷题Day15——二叉树（树左下角的值、路径和、树的构造、最大二叉树、合并二叉树）
一、找树左下角的值 题目链接：513. 找树左下角的值
得过且过的勇者y
45 0
刘牌
|
存储 算法
二叉树的创建和遍历
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分
刘牌
97 0
霸总爱吃鱿鱼虾
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
霸总爱吃鱿鱼虾
47 0
云与尘呀？
树的遍历
树的遍历
云与尘呀？
74 0
幼稚十一
|
存储 编译器
二叉树的递归遍历与迭代遍历（图示）
本文将讲述二叉树递归与迭代的相关知识。
幼稚十一
135 0
HannYang
|
机器学习/深度学习 C++ 容器
二叉树创建和遍历（C++实现）
树（Tree）是n(n≥0)个节点的有限集。在任意一棵树中有且仅有一个特定的称为根（Root）的节点；当n＞1时，其余节点可分m(m＞0)为个互不相交的有限集T1,T2,...,Tm；其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。 二叉树（Binary Tree）是一种特殊的有序树型结构，所有节点最多只有2棵子树。
HannYang
713 0
Lucky小黄人^_^
二叉查找树的建立，删除，非递归和递归查找给定元素，非递归和递归查找最大元素结点和最小元素结点
二叉查找树的建立，删除，非递归和递归查找给定元素，非递归和递归查找最大元素结点和最小元素结点
Lucky小黄人^_^
103 0