/*
题意:
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;
}
网友评论