題目：

A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.

In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.

In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.

In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.

Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.
Input
The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.
Output
For each test case print a single line specifying the corresponding postorder sequence.
Sample Input
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
Sample Output
7 4 2 8 9 5 6 3 1

分析與解答：

1.二叉樹有根結點，有兩個子結點，而且子結點數據類型和根節點相同，因此我們用struct存儲
2.根據題中給的數據建樹，先序后序中序，知道任意兩個就可以建樹
這題是給了中序和先序，左根右，根左右
主要問題就是根據遍歷的性質找根，然后遞歸建立左子樹右子樹

先序：1 2 4 7 3 5 8 9 6
中序：4 7 2 1 8 5 9 3 6
先序第一個1是根
所以從中序開始找，472應當是第一個根的左子樹
對應先序的247，可知，如果把左子樹從新看成二叉樹，那他的根就是2
再繼續找，把左子樹找完了
右子樹35896 根是3，然后繼續找

總結一下思想：
先創一個結點，他的根直接知道就是先序第一個數，先認為他沒有左右子結點（因為如果遞歸到最后一個子葉，他沒有子結點）
找到根后，通過遞歸調用，填他的左子樹的結點值右子樹的結點值

輸出的話如果后序，輸出：左子樹，右子樹，根
這題是由于空格的原因，我把數存到數組里了

#include <iostream> #include <cstdio> #include <cstring> #include<cstdlib> #include <algorithm> #define N 1000 using namespace std;struct TreeNote {int ch; TreeNote * ltree;TreeNote * rtree; }; TreeNote * CreatTree(int * preorder, int * inorder, int longth) {TreeNote * sontree = new TreeNote;sontree-> ch = *preorder;sontree-> ltree = NULL;sontree-> rtree = NULL;if(longth == 0)return NULL;int index = 0;for(; index < longth; index++)if(inorder[index] == *preorder)break;sontree-> ltree = CreatTree(preorder+1, inorder, index);sontree-> rtree = CreatTree(preorder+index+1, inorder+index+1, longth-index-1);return sontree; } int a[1000]; int p=0; void PostOrder(TreeNote * tone) {if(tone){PostOrder(tone-> ltree);PostOrder(tone-> rtree);a[p++]=tone->ch;} }int main() {int preorder[N];int inorder[N];int t; while(cin>>t){p=0;memset(a,0,sizeof(a));for(int i=0;i<t;++i){cin>>preorder[i];}for(int i=0;i<t;++i){cin>>inorder[i];}TreeNote * tone = CreatTree(preorder, inorder, t);PostOrder(tone);for(int i=0;i<p;++i){if(i!=p-1) cout<<a[i]<<' ';else cout<<a[i];} putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的（二叉树存储+递归遍历）Binary Tree Traversals的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。