【問題描寫敘述】

二叉樹
? ? ? ? ? ?A
? ? ? ?/ ? ? ? /
? ? ? ?B ? ? ? C
? ? ?/ ? / ? / ? /
? ? ?D ? E ? F ? G
? ? / / / / / / / /
? ? H I J K M N O P
后序遍歷的結(jié)果是：HIDJKEBMNFOPGCA，我們稱之為POST
中序遍歷的結(jié)果是：HDIBJEKAMFNCOGP，我們稱之為MID

【算法思想】
?(1)pi指向POST的最后一個(gè)字符
?(2)用pi從POST中取一個(gè)字符pc
?(3)查找pc在MID中出現(xiàn)的位置mi
?(4)依據(jù)mi確定pc與前一個(gè)字符的關(guān)系(左孩子/右孩子/沒有關(guān)系)
?(5)pi-1
?(6)重復(fù)重復(fù)(2)~(5)步，直到pi < 0

能夠看到，問題的關(guān)鍵在于步驟(4)，即怎樣確定pc與前一個(gè)字符的關(guān)系。
在這里我們要用到兩個(gè)輔助結(jié)構(gòu)：
?(1)一個(gè)鏈表，存放Helper結(jié)構(gòu)
?(2)一個(gè)Helper結(jié)構(gòu)，用于記錄每個(gè)節(jié)點(diǎn)在MID中的下標(biāo)
鏈表我們能夠用STL的list，Helper的結(jié)構(gòu)例如以下

struct Helper { TreeNode* node; int index; public: Helper(TreeNode* pNode, int idx) : node(pNode), index(idx) { } };當(dāng)然。二叉樹的節(jié)點(diǎn)也要有：

struct TreeNode {char data;TreeNode* lChild;TreeNode* rChild; public:TreeNode(char c) : data(c), lChild(0), rChild(0) { } };
好了，我們一步一步來看看怎樣解決這個(gè)還原二叉樹的問題
(1) (A, 7)
?取POST第一個(gè)字符。然后通過Helper放入list中，并構(gòu)造出一個(gè)list的初始環(huán)境
? ? ? ?0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
?POST: H I D J K E B M N F ?O ?P ?G ?C ?A
?MID: ?H D I B J E K A M F ?N ?C ?O ?G ?P
?【list】
?nod ?0 ? A ? 0
?idx -1 ? 7 ?15
?cur ? ? ?^
?nxt
?cur, nxt都是指向list中元素的指針。頭尾兩個(gè)元素表示邊界
(2) (C, 11)
?取POST第13個(gè)字符。依據(jù)list來判定它為誰(shuí)的左孩子/右孩子
?能夠看到。pc=C，其在MID中的下標(biāo)mi為11，簡(jiǎn)略為(C, 11)，以后都這么簡(jiǎn)略
?(C, 11)在(A, 7)右邊，由于11 > 7，所以C為A的右孩子，并插入到list中，注意
?cur指針的變動(dòng)。
? ? ? ?0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
?POST: H I D J K E B M N F ?O ?P ?G ?C ?A
?MID: ?H D I B J E K A M F ?N ?C ?O ?G ?P
?【list】
?nod ?0 ? A ? C ? 0
?idx -1 ? 7 ?11 ?15
?cur ? ? ? ? ?^
?nxt
(3) (G, 13)?
?(G, 13)在(C, 11)右邊，由于 13 > 11。所以G是C的右孩子。插入list中
?【list】
?nod ?0 ? A ? C ? G ? 0
?idx -1 ? 7 ?11 ?13 ?15
?cur ? ? ? ? ? ? ?^
?nxt
以下省略。由于這個(gè)和我的另外一篇文章《前序-中序二叉樹還原》非常像，僅僅只是一個(gè)從前往后
一個(gè)從后往前，另一個(gè)先確定左孩子，一個(gè)先確定右孩子罷了
以下講一下當(dāng)A的右子樹都還原好了，如何還原B的情況。同一時(shí)候也解說了如何還原左孩子的方法。

(12)(B, 3)?
?這個(gè)時(shí)候鏈表應(yīng)該是這種
?【list】
?nod ?0 ? A ? M ? 0
?idx -1 ? 7 ? 8 ?15
?cur ? ? ? ? ?^
?nxt?
?(B, 3)不在(M, 8)右邊，nxt = cur, cur--
?【list】
?nod ?0 ? A ? M ? 0
?idx -1 ? 7 ? 8 ?15
?cur ? ? ?^
?nxt ? ? ? ? ?^?
?(B, 3)不在(A, 7),(M, 8)中間。刪除(M, 8)
?【list】
?nod ?0 ? A ? 0
?idx -1 ? 7 ?15
?cur ? ? ?^
?nxt?
(13)(B, 3)?
?此時(shí)(B, 3)不在(A, 7)右邊。nxt = cur, cur--
?【list】
?nod ?0 ? A ? 0
?idx -1 ? 7 ?15
?cur ?^
?nxt ? ? ?^
?(B, 3)在(0, -1),(A, 7)中間，因此B是A的左孩子，刪除A，插入B，cur指向B
?【list】
?nod ?0 ? B ? 0
?idx -1 ? 3 ?15
?cur ? ? ?^
?nxt ? ? ??

對(duì)了，千萬不要忘記在確定X節(jié)點(diǎn)是Y節(jié)點(diǎn)的左/右孩子后要做對(duì)應(yīng)的鏈接操作。

以下給出算法的C++表示。這里我們用iterator來表示cur, nxt指針。

我們之所以要用list是
由于list在插入/刪除元素后iterator不會(huì)失效。另一點(diǎn)，由于list<>::iterator不支持
random access。所以我們要用nxt, cur兩個(gè)iterator表示一前一后，否則的話直接用cur和
cur - 1即可了，這種話就簡(jiǎn)單多了。
【源代碼實(shí)現(xiàn)】

#include <iostream> #include <stack> #include <string> #include <list> using namespace std; struct TreeNode {char data;TreeNode* lChild;TreeNode* rChild; public :TreeNode( char c) : data(c), lChild(0), rChild(0) { } }; struct Helper {TreeNode* node;int index; public :Helper(TreeNode* pNode, int idx) : node(pNode), index(idx) { } }; int main() {void inorderTraversal(TreeNode* pTree);void postorderTraversal(TreeNode* pTree);void Post_Mid_Restore(string post, string mid, TreeNode*& result);/* A/ /B C/ / / /D E F G/ / / / / / / /H I J KM N O P*/string Postorder1 = "HIDJKEBMNFOPGCA" ;string Midorder1 = "HDIBJEKAMFNCOGP" ;string Postorder2 = "DBFGECA";string Midorder2 = "BDAFEGC"; TreeNode* res = 0;Post_Mid_Restore(Postorder1, Midorder1, res);inorderTraversal(res);postorderTraversal(res);Post_Mid_Restore(Postorder2, Midorder2, res);inorderTraversal(res);postorderTraversal(res);cin.get(); } void print(list<Helper>& h) {list<Helper>::iterator iter = h.begin();for (; iter != h.end(); iter++) {if ((*iter).node == 0) {cout << 0 << ':' << (*iter).index << "; " ;}else {cout << (*iter).node->data << ':' << (*iter).index << "; " ;}}cout << endl; } //后序-中序-二叉樹還原 void Post_Mid_Restore(string post, string mid, TreeNode*& result) {int pi = post.size() - 1; //后序遍歷所得字符串的下標(biāo) int mi = 0; //中序遍歷所得字符串的下標(biāo)char pc; //后序遍歷的字符 result = new TreeNode(post[pi]); //后序遍歷的第一個(gè)字符是根節(jié)點(diǎn) TreeNode* pNode = 0;mi = mid.find(post[pi]); //在中序字符串中找到后序字符串的當(dāng)前字符位置 list<Helper> helper; helper.push_back(Helper(0, -1)); helper.push_back(Helper(result, mi));helper.push_back(Helper(0, mid.size()));list<Helper>::iterator cur = helper.begin();cur++;/*下標(biāo) -1 7 15節(jié)點(diǎn) 0 A 0cur ^*/for (pi = post.size() - 2; pi >= 0 ; pi--) {pc = post[pi]; //后序字符串的當(dāng)前字符 mi = mid.find(pc); //在中序字符串中的位置 while ( true ) {if (mi > (*cur).index) { //在右邊就是右孩子 pNode = new TreeNode(pc);(*cur).node->rChild = pNode;cur++;cur = helper.insert(cur, Helper(pNode, mi));break ; }else { //不在右邊list<Helper>::iterator nxt = cur;cur--;if ((*cur).index < mi && mi < (*nxt).index) { //在中間就是左孩子 pNode = new TreeNode(pc);(*nxt).node->lChild = pNode;helper.erase(nxt);cur++;cur = helper.insert(cur, Helper(pNode, mi));break ;} //不在中間就不是左孩子 else {helper.erase(nxt);continue ;}} }} } //中序遍歷 void inorderTraversal(TreeNode* pTree) {stack<TreeNode*> treeStack;do {while (pTree != 0) {treeStack.push(pTree);pTree = pTree->lChild;}if (!treeStack.empty()) {pTree = treeStack.top();treeStack.pop();cout << pTree->data;pTree = pTree->rChild;}} while (!treeStack.empty() || pTree != 0);cout << endl; } //后序遍歷 //后序遍歷的輔助結(jié)構(gòu) struct postorderHelper {TreeNode* ptr;int flag; public :postorderHelper(TreeNode* pTree) : ptr(pTree), flag(0) { } }; void postorderTraversal(TreeNode* pTree) {stack<postorderHelper> treeStack;do {while (pTree != 0) {treeStack.push(postorderHelper(pTree));pTree = pTree->lChild;}if (!treeStack.empty()) {if (treeStack.top().flag == 0) {treeStack.top().flag++;pTree = treeStack.top().ptr->rChild;}else {cout << treeStack.top().ptr->data;treeStack.pop();pTree = 0;}}} while (!treeStack.empty());cout << endl; }



<span style="font-family:Times New Roman;font-size:18px;">struct Helper {TreeNode* node;int index; public:Helper(TreeNode* pNode, int idx) : node(pNode), index(idx) { } };</span>當(dāng)然， 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的数据结构基础 后序遍历和中序遍历还原二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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