分享一下我老師大神的人工智能教程！零基礎(chǔ)，通俗易懂！http://blog.csdn.net/jiangjunshow

也歡迎大家轉(zhuǎn)載本篇文章。分享知識(shí)，造福人民，實(shí)現(xiàn)我們中華民族偉大復(fù)興！

題目出處

題意：輸入兩組數(shù)據(jù)，分別是前序遍歷序列和中序遍歷序列，你需要編寫程序通過這兩組數(shù)據(jù)求出該樹的后序遍歷序列（前序序列 + 中序序列 = 后序序列）

解法：遞歸

題目分析：

可以先按照用筆和紙的形式去推導(dǎo)出后序序列。推導(dǎo)過程省略，在推導(dǎo)過程中我們會(huì)發(fā)現(xiàn)規(guī)律：

假設(shè) 前序序列是 A B E H F C G I

?中序序列是 H E B F A C I G （圖如下）

每一次從前序序列里，按順序抽取出字母就能將中序序列分割，并根據(jù)中序遍歷的特性。分割后的兩部分分別是 左子樹 和 右子樹（注意，他們也是二叉樹！）

就像這樣：取A， 中序序列被分割為 左子樹：H E B F ?右子樹 C I G

繼續(xù)取B，但是這次是對左子樹：H E B F 進(jìn)行分割。 分割結(jié)果是：?左子樹：H E ?右子樹 ?B F

直到不能再分割，遞歸會(huì)返回去到第一次使用 A 分割出來的 右子樹 里繼續(xù)分割

上述整個(gè)過程都是遞歸，所以結(jié)合代碼和用紙筆畫一次會(huì)更好理解

代碼：

#include <stdio.h>#include <stdlib.h>typedef struct TreeNode{?char??? data;?struct TreeNode?? *lchild;?struct TreeNode?? *rchild;} Node, *PNode;char???? preorder[28];?? //存放前序序列char???? infix[28];? //存放中序序列char??? *Pr;void build(char *in, char *pr, PNode *tr);void postordertraversal(PNode T);int main(){?//先建樹、再后序遍歷輸出?PNode??? T;??while(scanf("%s %s", &preorder[1], &infix[1]) == 2)?{??build(&infix[1], &preorder[1], &T);??postordertraversal(T);??printf("\n");?}?return??? 0;}void build(char *in, char *pr, PNode *tr){?char??? *p = in;?Pr = pr;?if (*in == 0)?{??*tr = NULL;??return;?}?while (1)?{??if (*in == *Pr)??{???(*tr) = (PNode)malloc(sizeof(Node));???(*tr)->data = *Pr;???*in = 0;???break;??}??in++;?}?Pr = Pr + 1;?build(p, Pr, &(*tr)->lchild);?build(in+1, Pr, &(*tr)->rchild);}void postordertraversal(PNode T){?if (T == NULL)??return;?postordertraversal(T->lchild);?postordertraversal(T->rchild);?printf("%c", T->data);}
這份代碼有些東西需要注意：

• 這里使用到指針，其實(shí)可以不使用指針的，下面介紹的更精巧的解法就是用下標(biāo)的。能盡量不用指針就盡量不用
• 注意指向指針的指針在這里的作用，這里有講解

上面的解法是比較直接容易想到的，所以代碼沒有很精巧。而這里有份更好的解法！

???????????

給我老師的人工智能教程打call！http://blog.csdn.net/jiangjunshow

總結(jié)

以上是生活随笔為你收集整理的poj 2255 Tree Recovery 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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