美文网首页
A1020 Tree Traversals (25分)

A1020 Tree Traversals (25分)

作者: km15 | 来源:发表于2020-03-06 18:39 被阅读0次

/*
题意:
1、给出后序跟中序,求出层序遍历

解题:
1、两个数组,然后读入中序跟后序
2、调用函数,返回一个根节点
3、层次遍历(即广度优先遍历)

learn && wrong:
1、n是全局变量
2、递归边界,可以返回NULL
3、没有初始化指针,一定要先new或者malloc
4、记得,呀,是跟postorder的[postR]比较
5、后序的左子树从0inL开始,要减一的
6、注意,最后一个不要空格的写法,其实就是加一个if,本质还是那个套路

*/

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node {
    int data;
    Node* lchild;
    Node* rchild;
}node;

const int maxn = 50;

int postorder[maxn], inorder[maxn], preorder[maxn];
int n; //!!!

Node* create(int postL,int postR,int inL,int inR) {
    if (postL > postR) {
        return NULL; // return NULL!!!
    }
    Node* root = new Node;  //!!!没初始化
    root->data = postorder[postR];   //找到根节点    //
    int i;
    for (i = inL;i <= inR;i++) {//!!!
        if (inorder[i] == postorder[postR]) {//!!!!
            break;
        }
    }

    int leftNum = i - inL;
    //后序的左子树为postL,postL + leftNum, 中序为inL, i - 1

    root->lchild = create(postL, postL + leftNum - 1, inL, i - 1);  //后序的左子树没-1!!!

    //后序的右子树为posL + leftnum,postR - 1,中序为,i + 1,inR
    root->rchild = create(postL + leftNum, postR - 1, i + 1, inR);
    
    return root;    //返回节点了吗
}

//层次遍历
int num = 0;    //!!!已经输出的节点个数
void levelorder(Node* root) {
    queue<Node*> q;
    q.push(root);

    while(!q.empty()) {
        Node* now = q.front();
        q.pop();    //弹出
        printf("%d", now->data);
        num++;
        if (num < n) cout << " ";
        if (now->lchild != NULL) {
            q.push(now->lchild);
        }
        if (now->rchild != NULL) {
            q.push(now->rchild);
        }
    }
}

int main()
{
    
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> postorder[i];
    }
    for (int i = 0;i < n;i++) {
        cin >> inorder[i];
    }

    
    Node* root1 = create(0, n - 1, 0, n - 1);   //!!!

    levelorder(root1);
    return 0;
}

相关文章

网友评论

      本文标题:A1020 Tree Traversals (25分)

      本文链接:https://www.haomeiwen.com/subject/ddfwrhtx.html