L2-006. 树的遍历

已知二叉树的后序遍历和中序遍历,求出它的层序遍历

与前两个不同的是,层序遍历必须先建立一个树,然后BFS,就是广度优先搜索,不懂的话可以看【这篇文章】

由于树的节点只能用指针指向,所以建立指针数组,再遍历就OK了。

/* 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 * 4 1 6 3 5 7 2 */
#include<iostream>
#include<cstring>
#include<cstdlib>
typedef struct node
{
    struct node *left;
    struct node *right;
    int data;
}Node;
using namespace std;
Node *binarytree(int a[],int b[],int len)
{
    int i;
    if (len==0)
    return NULL;
    Node *tree;
    tree=(Node *)malloc(sizeof(Node));
    tree->data=a[len-1];
    for (i=0;i<len;i++)
    {
        if (b[i]==a[len-1])
        break;
    }
    tree->left=binarytree(a,b,i);
    tree->right=binarytree(a+i,b+i+1,len-i-1);
    return tree;
}
int main()
{
    int n;
    cin>>n;
    int mid[n],next[n];
    for (int i=0;i<n;i++)
    cin>>next[i];
    for (int i=0;i<n;i++)
    cin>>mid[i];
    Node *que[n];
    int head=0,tail=0;
    que[tail++]=binarytree(next,mid,n);
    while (head<tail)
    {
        cout<<que[head]->data;
        if (head!=n-1)
        cout<<" ";
        if (que[head]->left!=NULL)
        que[tail++]=que[head]->left;
        if (que[head]->right!=NULL)
        que[tail++]=que[head]->right;
        head++;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务