数据结构基础 后序遍历和中序遍历还原二叉树

【问题描写叙述】

二叉树
           A
       /       /
       B       C
     /   /   /   /
     D   E   F   G
    / / / / / / / /
    H I J K M N O P
后序遍历的结果是：HIDJKEBMNFOPGCA，我们称之为POST
中序遍历的结果是：HDIBJEKAMFNCOGP，我们称之为MID

【算法思想】
 (1)pi指向POST的最后一个字符
 (2)用pi从POST中取一个字符pc
 (3)查找pc在MID中出现的位置mi
 (4)依据mi确定pc与前一个字符的关系(左孩子/右孩子/没有关系)
 (5)pi-1
 (6)重复重复(2)~(5)步，直到pi < 0

能够看到，问题的关键在于步骤(4)，即怎样确定pc与前一个字符的关系。
在这里我们要用到两个辅助结构：
 (1)一个链表，存放Helper结构
 (2)一个Helper结构，用于记录每个节点在MID中的下标
链表我们能够用STL的list，Helper的结构例如以下

struct Helper { TreeNode* node; int index; public: Helper(TreeNode* pNode, int idx) : node(pNode), index(idx) { } };当然。二叉树的节点也要有：

struct TreeNode {char data;TreeNode* lChild;TreeNode* rChild; public:TreeNode(char c) : data(c), lChild(0), rChild(0) { } };
好了，我们一步一步来看看怎样解决这个还原二叉树的问题
(1) (A, 7)
 取POST第一个字符。然后通过Helper放入list中，并构造出一个list的初始环境
       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中元素的指针。头尾两个元素表示边界
(2) (C, 11)
 取POST第13个字符。依据list来判定它为谁的左孩子/右孩子
 能够看到。pc=C，其在MID中的下标mi为11，简略为(C, 11)，以后都这么简略
 (C, 11)在(A, 7)右边，由于11 > 7，所以C为A的右孩子，并插入到list中，注意
 cur指针的变动。
       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
以下省略。由于这个和我的另外一篇文章《前序-中序二叉树还原》非常像，仅仅只是一个从前往后
一个从后往前，另一个先确定左孩子，一个先确定右孩子罢了
以下讲一下当A的右子树都还原好了，如何还原B的情况。同一时候也解说了如何还原左孩子的方法。

(12)(B, 3) 
 这个时候链表应该是这种
 【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) 
 此时(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       

对了，千万不要忘记在确定X节点是Y节点的左/右孩子后要做对应的链接操作。

以下给出算法的C++表示。这里我们用iterator来表示cur, nxt指针。

我们之所以要用list是
由于list在插入/删除元素后iterator不会失效。另一点，由于list<>::iterator不支持
random access。所以我们要用nxt, cur两个iterator表示一前一后，否则的话直接用cur和
cur - 1即可了，这种话就简单多了。
【源代码实现】

#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; //后序遍历所得字符串的下标 int mi = 0; //中序遍历所得字符串的下标char pc; //后序遍历的字符 result = new TreeNode(post[pi]); //后序遍历的第一个字符是根节点 TreeNode* pNode = 0;mi = mid.find(post[pi]); //在中序字符串中找到后序字符串的当前字符位置 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++;/*下标 -1 7 15节点 0 A 0cur ^*/for (pi = post.size() - 2; pi >= 0 ; pi--) {pc = post[pi]; //后序字符串的当前字符 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; } //后序遍历 //后序遍历的辅助结构 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>当然， 新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的数据结构基础 后序遍历和中序遍历还原二叉树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。