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

心已赠人 2022-08-04 10:54 186阅读 0赞

【问题描述】

二叉树  
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       0
            cur                  ^
        */
         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>

当然，