网站到首页排名,昆明城乡建设网站,工程建设标准最新查询网站,慈溪白云小学班级网站建设题目描述#xff1a;给出二叉树的后序和中序序列#xff0c;输出二叉树的层序遍历序列。
题目分析#xff1a;中序遍历为左根右#xff0c;后序遍历为左右根#xff0c;所以后序遍历的最后一个节点为根节点#xff0c;在中序遍历上找出根节点的位置#xff0c;将树分为…题目描述给出二叉树的后序和中序序列输出二叉树的层序遍历序列。
题目分析中序遍历为左根右后序遍历为左右根所以后序遍历的最后一个节点为根节点在中序遍历上找出根节点的位置将树分为左右两个子树。
使用 in[]post[] 存储中序后后序序列。假设某个分支二叉树中序区间为[inL, inR]后序区间为[postLpostR]那么post[postR]就为该树的根节点根据根节点去中序中查找找到根节点在中序中的位置为k。二叉树左子树的个数为numLeftk-inL。左子树的中序区间为[inL,k-1]右子树的中序区间[k1,inR]左子树的后序区间为[postL,postLnumLeft-1]右子树的后序区间为[postLnumLeft,postR-1]。
创建树时返回根节点的地址。最后层序遍历树使用队列从根节点开始将节点入队然后读队首再出队直至队列为空。
代码如下
#include iostream
#include queue
using namespace std;
const int N 1010;
int in_order[N], post_order[N];
int n;struct node {int data;node *lchild;node *rchild;
};node *build(int inL, int inR, int postL, int postR) {if (inL inR)return NULL;node *root;root new node;root-data post_order[postR];int k inL;while (in_order[k] ! root-data)k;int numLeft k - inL;root-lchild build(inL, k - 1, postL, postL numLeft - 1);root-rchild build(k 1, inR, postL numLeft, postR - 1);return root;
}void bfs(node *root) {int num 0;queuenode *q;q.push(root);while (q.size()) {node *now q.front();q.pop();cout 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 in_order[i];for (int i 0; i n; i)cin post_order[i];node *root build(0, n - 1, 0, n - 1);bfs(root);return 0;
}测试结果
题目分析链接 https://blog.csdn.net/weixin_39851956/article/details/105253197
