1020 Tree Traversals（二叉树，DLR/LDR求层次排列）

小灰灰 2024-04-08 09:41 36阅读 0赞

## 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 N N ( ≤ 30 ≤30 ≤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、基本思路 ###

<table> 
 <thead> 
  <tr> 
   <th>序号</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>postorder</code></td> 
   <td>2</td> 
   <td>3</td> 
   <td>1</td> 
   <td>5</td> 
   <td>7</td> 
   <td>6</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td><code>inorder</code></td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
  </tr> 
 </tbody> 
</table>

可以拿上面那个模拟一下，树长这样

![在这里插入图片描述][923dee6b7c4f4e8b857027e7c369df93.png]

### 3、解题过程 ###

这里给大家安利一个[**二叉树**和**哈夫曼树**在线绘制网站][Link 1]。如果感兴趣，可以看附件的 `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;
    }

![在这里插入图片描述][7b6d26dd93214c52a7dba2d60205ebad.png]

### 3.2 附件 - 在线绘制二叉树 ###

<!DOCTYPE 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">
        
        <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>

[923dee6b7c4f4e8b857027e7c369df93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/6e2660ef8ead47d288d8f1467e42b87b.png
[Link 1]: http://www.easycode.top/
[7b6d26dd93214c52a7dba2d60205ebad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/6431e47c54ff4df78ba24a9113d0bef5.png