根據後序和中序遍歷輸出先序遍歷
- 2019 年 11 月 8 日
- 筆記
版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/85331082
題目描述：
本題要求根據給定的一棵二叉樹的後序遍歷和中序遍歷結果，輸出該樹的先序遍歷結果。
輸入格式:
第一行給出正整數N(≤30)，是樹中結點的個數。隨後兩行，每行給出N個整數，分別對應後序遍歷和中序遍歷結果，數字間以空格分隔。題目保證輸入正確對應一棵二叉樹。
輸出格式:
在一行中輸出Preorder:以及該樹的先序遍歷結果。數字間有1個空格，行末不得有多餘空格。
輸入樣例:
7 2 3 1 5 7 6 4 1 2 3 4 5 6 7
輸出樣例:
Preorder: 4 1 3 2 6 5 7
相關知識：
1.先序遍歷的遞歸過程為：若二叉樹為空，遍歷結束。否則：①訪問根結點；②先序遍歷根結點的左子樹；③先序遍歷根結點的右子樹。 簡單來說先序遍歷就是在深入時遇到結點就訪問。
2.中序遍歷的遞歸過程為：若二叉樹為空，遍歷結束。否則：①中序遍歷根結點的左子樹；②訪問根結點；③中序遍歷根結點的右子樹。簡單來說中序遍歷就是從左子樹返回時遇到結點就訪問。
3.後序遍歷的遞歸過程為：若二叉樹為空，遍歷結束。否則：①後序遍歷根結點的左子樹；②後序遍歷根結點的右子樹；③訪問根結點。簡單來說後序遍歷就是從右子樹返回時遇到結點就訪問。
AC程式碼：
#include <bits/stdc++.h> using namespace std; void getpre(int *postorder,int *inorder,int n) //其中數組postorder為後序,inorder為中序,n為每次遍曆數目 { if(n>0) { int root = postorder[n-1]; //根結點為後序遍歷的最後一個 int i; for(i = 0; i < n; i++) //在中序遍歷中查找根結點 { if(inorder[i] == root) { break; } } cout << " " << root; getpre(postorder, inorder, i); //對左子樹來查找根結點 getpre(postorder+i, inorder+i+1, n-i-1); //對右子樹來查找根結點 } } int main() { int n; cin >> n; int postorder[n],inorder[n]; //postorder[n]後序 inorder[n]中序 for(int i=0;i<n;i++) { cin >> postorder[i]; //輸入後序 } for(int i=0;i<n;i++) { cin >> inorder[i]; //輸入中序 } cout << "Preorder:"; getpre(postorder,inorder,n); return 0; }
