一、已知先序遍歷和中序遍歷，求后序遍歷。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=944

根據(jù)先序遍歷和中序遍歷還原二叉樹的主要思想：

1、先序遍歷序列的第一個(gè)元素必定是根節(jié)點(diǎn)，可以由此獲取二叉樹的根節(jié)點(diǎn)。

2、根據(jù)根節(jié)點(diǎn)，在中序遍歷序列中查找該節(jié)點(diǎn)，由中序遍歷的性質(zhì)可知，中序遍歷中該根節(jié)點(diǎn)左邊的序列必定在根節(jié)點(diǎn)的左子樹中，而根節(jié)點(diǎn)右邊的序列必定在右子樹中。由此可以知道先序遍歷中左子樹以及右子樹的起止位置。

3、分別對(duì)左子樹和右子樹重復(fù)上述的過程，直至所有的子樹的起止位置相等時(shí)，說明已經(jīng)到達(dá)葉子節(jié)點(diǎn)，遍歷完畢。

實(shí)現(xiàn)代碼：

#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

根據(jù)中序遍歷和后序遍歷還原二叉樹的主要思想：

1、后序遍歷序列的最后一個(gè)元素必定是根節(jié)點(diǎn)，可以由此獲取二叉樹的根節(jié)點(diǎn)。

2、根據(jù)根節(jié)點(diǎn)，在中序遍歷序列中查找該節(jié)點(diǎn)，由中序遍歷的性質(zhì)可知，中序遍歷中該根節(jié)點(diǎn)左邊的序列必定在根節(jié)點(diǎn)的左子樹中，而根節(jié)點(diǎn)右邊的序列必定在右子樹中。由此可以知道后序遍歷中左子樹以及右子樹的起止位置。

3、分別對(duì)左子樹和右子樹重復(fù)上述的過程，直至所有的子樹的起止位置相等時(shí)，說明已經(jīng)到達(dá)葉子節(jié)點(diǎn)，遍歷完畢。

實(shí)現(xiàn)代碼：

#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; }

總結(jié)

以上是生活随笔為你收集整理的二叉树重建的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。