1020 Tree Traversals #
0、题目 #
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification: #
Each input file contains one test case. For each case, the first line gives a positive integer $N$ ($≤30$), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification: #
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input: #
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output: #
4 1 6 3 5 7 2
1、大致题意 #
给出二叉树的先序和中序排列，求层次排列。
2、基本思路 #
序号0123456postorder2315764inorder1234567
可以拿上面那个模拟一下，树长这样
3、解题过程 #
这里给大家安利一个
二叉树和哈夫曼树在线绘制网站。如果感兴趣，可以看附件的 html 文件。
3.1 AC代码 #
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 50;
struct node {
int data;
node* lchild;
node* rchild;
};
int n;
int pre[maxn], in[maxn], post[maxn];
node* create(int postL, int postR, int inL, int inR) {
if(postL > postR) return NULL;
node* root = new node;
root->data = post[postR];
int k;
for(k=inL; k<=inR; k++) {
if(in[k] == post[postR]) {
break;
}
}
int numLeft = k -inL;
root->lchild = create(postL, postL + numLeft -1, inL, k-1);
root->rchild = create(postL + numLeft, postR-1, k+1, inR);
return root;
}
void BFS(node* root) {
queue<node*> q;
q.push(root);
int num = 0;
while(!q.empty()) {
node* now = q.front();
q.pop();
printf("%d", now->data);
num++;
if(num < n) printf(" ");
if(now->lchild != NULL) q.push(now->lchild);
if(now->rchild != NULL) q.push(now->rchild);
}
}
int main() {
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%d",&post[i]);
}
for(int i=0; i<n; i++) {
scanf("%d",&in[i]);
}
node* root = create(0, n-1, 0, n-1);
BFS(root);
return 0;
}
3.2 附件 - 在线绘制二叉树 #
<!DOCTYPE html>
<!-- saved from url=(0039)http://www.easycode.top/binarytree.html -->
<html lang="zh"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><script charset="utf-8" src="./二叉树_files/UrlChangeTracker.js.下载"></script><script src="./二叉树_files/f.txt"></script><script src="./二叉树_files/f(1).txt" id="google_shimpl"></script><script src="./二叉树_files/hm.js.下载"></script><script>
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "https://hm.baidu.com/hm.js?50dd33792a91ed9832a6345b5162f0a6";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
</script>
<script async="" src="./二叉树_files/f(2).txt" crossorigin="anonymous" data-checked-head="true"></script>
<meta name="baidu_union_verify" content="1fa00acc28e7b488e6c9d6b1ad72b157">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>二叉树</title>
<meta name="renderer" content="webkit|ie-comp|ie-stand">
<meta name="keywords" content="二叉树,在线二叉树转换,前序,后序,中序,求后序,求前序,构建二叉树">
<meta name="description" content="heaboy作为一个在线工具提供者,立志于提供更多方便的在线工具">
<link rel="shortcut icon" type="image/x-icon" href="http://www.easycode.top/static/favicon.ico">
<!-- 最新版本的 Bootstrap 核心 CSS 文件 -->
<link rel="stylesheet" href="./二叉树_files/bootstrap.min.css" integrity="sha384-HSMxcRTRxnN+Bdg0JdbxYKrThecOKuH5zCYotlSAcp1+c8xmyTe9GYg1l9a69psu" crossorigin="anonymous">
<meta http-equiv="origin-trial" content="AzoawhTRDevLR66Y6MROu167EDncFPBvcKOaQispTo9ouEt5LvcBjnRFqiAByRT+2cDHG1Yj4dXwpLeIhc98/gIAAACFeyJvcmlnaW4iOiJodHRwczovL2RvdWJsZWNsaWNrLm5ldDo0NDMiLCJmZWF0dXJlIjoiUHJpdmFjeVNhbmRib3hBZHNBUElzIiwiZXhwaXJ5IjoxNjYxMjk5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><meta http-equiv="origin-trial" content="A6+nc62kbJgC46ypOwRsNW6RkDn2x7tgRh0wp7jb3DtFF7oEhu1hhm4rdZHZ6zXvnKZLlYcBlQUImC4d3kKihAcAAACLeyJvcmlnaW4iOiJodHRwczovL2dvb2dsZXN5bmRpY2F0aW9uLmNvbTo0NDMiLCJmZWF0dXJlIjoiUHJpdmFjeVNhbmRib3hBZHNBUElzIiwiZXhwaXJ5IjoxNjYxMjk5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><meta http-equiv="origin-trial" content="A/9La288e7MDEU2ifusFnMg1C2Ij6uoa/Z/ylwJIXSsWfK37oESIPbxbt4IU86OGqDEPnNVruUiMjfKo65H/CQwAAACLeyJvcmlnaW4iOiJodHRwczovL2dvb2dsZXRhZ3NlcnZpY2VzLmNvbTo0NDMiLCJmZWF0dXJlIjoiUHJpdmFjeVNhbmRib3hBZHNBUElzIiwiZXhwaXJ5IjoxNjYxMjk5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><meta http-equiv="origin-trial" content="AzoawhTRDevLR66Y6MROu167EDncFPBvcKOaQispTo9ouEt5LvcBjnRFqiAByRT+2cDHG1Yj4dXwpLeIhc98/gIAAACFeyJvcmlnaW4iOiJodHRwczovL2RvdWJsZWNsaWNrLm5ldDo0NDMiLCJmZWF0dXJlIjoiUHJpdmFjeVNhbmRib3hBZHNBUElzIiwiZXhwaXJ5IjoxNjYxMjk5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><meta http-equiv="origin-trial" content="A6+nc62kbJgC46ypOwRsNW6RkDn2x7tgRh0wp7jb3DtFF7oEhu1hhm4rdZHZ6zXvnKZLlYcBlQUImC4d3kKihAcAAACLeyJvcmlnaW4iOiJodHRwczovL2dvb2dsZXN5bmRpY2F0aW9uLmNvbTo0NDMiLCJmZWF0dXJlIjoiUHJpdmFjeVNhbmRib3hBZHNBUElzIiwiZXhwaXJ5IjoxNjYxMjk5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><meta http-equiv="origin-trial" content="A/9La288e7MDEU2ifusFnMg1C2Ij6uoa/Z/ylwJIXSsWfK37oESIPbxbt4IU86OGqDEPnNVruUiMjfKo65H/CQwAAACLeyJvcmlnaW4iOiJodHRwczovL2dvb2dsZXRhZ3NlcnZpY2VzLmNvbTo0NDMiLCJmZWF0dXJlIjoiUHJpdmFjeVNhbmRib3hBZHNBUElzIiwiZXhwaXJ5IjoxNjYxMjk5MTk5LCJpc1N1YmRvbWFpbiI6dHJ1ZSwiaXNUaGlyZFBhcnR5Ijp0cnVlfQ=="><link rel="preload" href="./二叉树_files/f(3).txt" as="script"><script type="text/javascript" src="./二叉树_files/f(3).txt"></script><script src="chrome-extension://mooikfkahbdckldjjndioackbalphokd/assets/prompt.js"></script></head>
<body>
<header>
<div class="head">
<div class="container">
<ul class="nav navbar-nav">
<li><a href="http://www.easycode.top/binarytree.html">二叉树</a></li>
<li><a href="http://www.easycode.top/huffman.html">哈夫曼树</a></li>
</ul>
</div>
</div>
</header>
<div class="container-fluid">
<div class="row">
<div class="col-md-4">
<blockquote>
<div><strong>中序是必须的,</strong>只有前序和后序，树基本上不唯一</div>
</blockquote>
<div class="form form-horizontal">
<div class="form-group">
<label for="pre" class="col-sm-2 control-label">前序</label>
<div class="col-sm-10">
<input class="form-control" type="text" name="pre" id="pre" value="">
</div>
</div>
<div class="form-group">
<label for="mid" class="col-sm-2 control-label">中序</label>
<div class="col-sm-10">
<input class="form-control" type="text" name="mid" id="mid" value="HDIBEJAFKCG">
</div>
</div>
<div class="form-group">
<label for="back" class="col-sm-2 control-label">后序</label>
<div class="col-sm-10">
<input class="form-control" type="text" name="back" id="back" value="HIDJEBKFGCA">
</div>
</div>
<div class="form-group">
<div class="col-sm-offset-10 col-sm2">
<button class="btn btn-primary btn-lg" onclick="compute()">走你</button>
</div>
</div>
</div>
</div>
<div class="col-md-8 text-center">
<canvas id="canvas" width="600" height="600">
您的浏览器不支持图形,请升级浏览器
</canvas>
</div>
</div>
</div>
<script async="" src="./二叉树_files/f(2).txt" crossorigin="anonymous" data-checked-head="true"></script>
<!-- 头广告 -->
<ins class="adsbygoogle" style="display: block; height: 280px;" data-ad-client="ca-pub-2380949900461835" data-ad-slot="5565476897" data-ad-format="auto" data-full-width-responsive="true" data-adsbygoogle-status="done" data-ad-status="unfilled"><div id="aswift_1_host" tabindex="0" title="Advertisement" aria-label="Advertisement" style="border: none; height: 280px; width: 1200px; margin: 0px; padding: 0px; position: relative; visibility: visible; background-color: transparent; display: inline-block; overflow: visible;"><iframe id="aswift_1" name="aswift_1" style="left:0;position:absolute;top:0;border:0;width:1200px;height:280px;" sandbox="allow-forms allow-popups allow-popups-to-escape-sandbox allow-same-origin allow-scripts allow-top-navigation-by-user-activation" width="1200" height="280" frameborder="0" marginwidth="0" marginheight="0" vspace="0" hspace="0" allowtransparency="true" scrolling="no" src="./二叉树_files/ads.html" data-google-container-id="a!2" data-load-complete="true"></iframe></div></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
<footer>
<div id="beian" class="text-center" style="margin-top: 60px;">
<a href="https://beian.miit.gov.cn/#/Integrated/recordQuery" target="_black">冀ICP备2021023452号-1</a>
</div>
</footer>
<script src="./二叉树_files/binarytree.js.下载"></script>
<script>
var compute = function () {
let pre = document.getElementById("pre").value;
let mid = document.getElementById("mid").value;
let back = document.getElementById("back").value;
let preArray = new Array();
preArray = pre.split("");
let midArray = new Array();
midArray = mid.split("");
let backArray = new Array();
backArray = back.split("");
console.log(preArray);
if (midArray.length == 0) {
console.log("中序为空");
alert("中序不得为空");
return;
}
if (preArray.length == 0) {
console.log("前序为空");
let root = backMid(midArray, backArray);
draw(root, 0, 600, 25);
let prearr = preorder(root);
document.getElementById("pre").value = prearr.join("");
} else if (backArray.length == 0) {
console.log("后序为空");
let root = preMid(preArray, midArray);
draw(root, 0, 600, 25);
let post = postorder(root);
document.getElementById("back").value = post.join("");
}
}
var backMid = function (midArr, backArr) {
if (!midArr || midArr.length === 0 || !backArr || backArr.length === 0 || midArr === backArr) return null;
// 获取后序的最后一个值为根节点, 获取中序的根节点的位置，分割成左右子树; 获取中序的左子树， 右子树， 获取后序的左子树和右子树
let rootNode = new BinTree(backArr[backArr.length - 1]);
let index = midArr.indexOf(backArr[backArr.length - 1]);
let midArrLeft = midArr.slice(0, index);
let midArrRight = midArr.slice(index + 1, midArr.length);
let backArrLeft = backArr.slice(0, index);
let backArrRight = backArr.slice(index, backArr.length - 1);
rootNode.left = backMid(midArrLeft, backArrLeft);
rootNode.right = backMid(midArrRight, backArrRight);
return rootNode;
}
var preMid = function (preArr, midArr) {
if (!preArr || preArr.length === 0 || !midArr || midArr.length === 0 || preArr === midArr) return null;
// 获取前序遍历的跟节点, 左子树的长度, 前序左子树，前序右子树， 中序左子树， 中序右子树
let rootNode = new BinTree(preArr[0]);
let index = midArr.indexOf(preArr[0]);
let preArrLeft = preArr.slice(1, index + 1);
let preArrRight = preArr.slice(index + 1);
let midArrLeft = midArr.slice(0, index);
let midArrRight = midArr.slice(index + 1);
rootNode.left = preMid(preArrLeft, midArrLeft);
rootNode.right = preMid(preArrRight, midArrRight);
return rootNode;
}
</script>
<ins class="adsbygoogle adsbygoogle-noablate" data-adsbygoogle-status="done" style="display: none !important;" data-ad-status="unfilled"><div id="aswift_0_host" tabindex="0" title="Advertisement" aria-label="Advertisement" style="border: none; height: 0px; width: 0px; margin: 0px; padding: 0px; position: relative; visibility: visible; background-color: transparent; display: inline-block;"><iframe id="aswift_0" name="aswift_0" style="left:0;position:absolute;top:0;border:0;width:undefinedpx;height:undefinedpx;" sandbox="allow-forms allow-popups allow-popups-to-escape-sandbox allow-same-origin allow-scripts allow-top-navigation-by-user-activation" frameborder="0" marginwidth="0" marginheight="0" vspace="0" hspace="0" allowtransparency="true" scrolling="no" src="./二叉树_files/ads(1).html" data-google-container-id="a!1" data-load-complete="true"></iframe></div></ins></body><iframe id="google_esf" name="google_esf" src="./二叉树_files/zrt_lookup.html" style="display: none;"></iframe></html>