一、已知先序遍歷和中序遍歷。求后序遍歷。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=944
依據先序遍歷和中序遍歷還原二叉樹的主要思想：
1、先序遍歷序列的第一個元素必然是根節點，能夠由此獲取二叉樹的根節點。
2、依據根節點，在中序遍歷序列中查找該節點。由中序遍歷的性質可知。中序遍歷中該根節點左邊的序列必然在根節點的左子樹中，而根節點右邊的序列必然在右子樹中。由此能夠知道先序遍歷中左子樹以及右子樹的起止位置。
3、分別對左子樹和右子樹反復上述的過程，直至全部的子樹的起止位置相等時。說明已經到達葉子節點，遍歷完成。
實現代碼：
#include<cstdio>
#include<cstring>
#include<cstdlib>
struct Node
{char value;Node *left, *right;
};
Node *build_new_node(char ch)
{Node *p = (Node*)malloc(sizeof(Node));p->value = ch;p->left = p->right = NULL;return p;
}
Node *Rebuild(char *pre, char *in, int n)
{if(n == 0) return NULL;char ch = pre[0];Node *p = build_new_node(ch);int i;for(i = 0; i < n && in[i] != ch; i++);int l_len = i;int r_len = n - i - 1;if(l_len > 0) p->left = Rebuild(pre+1, in, l_len);if(r_len > 0) p->right = Rebuild(pre+l_len+1, in+l_len+1, r_len);return p;
}
void PostOrder(Node *p)
{if(p == NULL) return ;PostOrder(p->left);PostOrder(p->right);printf("%c",p->value);
}
int main()
{char PreOrder[100], inOrder[100];while(~scanf("%s%s",PreOrder, inOrder)){Node *root = Rebuild(PreOrder,inOrder,strlen(PreOrder));PostOrder(root);printf("\n");}return 0;
}二、已知中序遍歷和后序遍歷，求先序遍歷。
http://acm.nyist.net/JudgeOnline/problem.php?pid=756
依據中序遍歷和后序遍歷還原二叉樹的主要思想：
1、后序遍歷序列的最后一個元素必然是根節點，能夠由此獲取二叉樹的根節點。
2、依據根節點，在中序遍歷序列中查找該節點，由中序遍歷的性質可知，中序遍歷中該根節點左邊的序列必然在根節點的左子樹中，而根節點右邊的序列必然在右子樹中。
由此能夠知道后序遍歷中左子樹以及右子樹的起止位置。
3、分別對左子樹和右子樹反復上述的過程，直至全部的子樹的起止位置相等時，說明已經到達葉子節點。遍歷完成。
實現代碼：
#include<cstdio>
#include<cstring>
#include<cstdlib>
struct Node
{char value;Node *left, *right;
};
Node *build_new_node(char ch)
{Node *p = (Node*)malloc(sizeof(Node));p->value = ch;p->left = p->right = NULL;return p;
}
Node *Rebuild(char *post, char *in, int n)
{if(n == 0) return NULL;char ch = post[n-1];Node *p = build_new_node(ch);int i;for(i = 0; i < n && in[i] != ch; i++);int l_len = i;int r_len = n - i - 1;if(l_len > 0) p->left = Rebuild(post, in, l_len);if(r_len > 0) p->right = Rebuild(post + l_len, in+l_len+1, r_len);return p;
}
void PreOrder(Node *p)
{if(p == NULL) return ;printf("%c",p->value);PreOrder(p->left);PreOrder(p->right);
}
int main()
{char PostOrder[100], InOrder[100];while(~scanf("%s%s",PostOrder, InOrder)){Node *root = Rebuild(PostOrder,InOrder,strlen(PostOrder));PreOrder(root);printf("\n");}return 0;
}
