根据层次遍历和中序遍历的结果还原一颗二叉树

我会带着你远行 2022-06-05 11:10 92阅读 0赞

转自:[http://blog.csdn.net/matrixdwy/article/details/3111808][http_blog.csdn.net_matrixdwy_article_details_3111808]

此文件描述了根据层次遍历，中序遍历的结果来还原二叉树的算法

我们先分别给出一个层次遍历，和一个中序遍历的结果字符串  
层次 A B C D E F G  
中序 D B A F E G C  
其对应的二叉树是：  
A  
/ /  
B C  
/ /  
D E  
/ /  
F G  
接下来详细讲解如果还原这棵二叉树的步骤，我用LEV代表层次遍历  
MID代表中序遍历。然后我们还需要一个HLP数组用来存放节点指针，  
其长度和层次/中序遍历字符串长度一样，并且其对应于中序遍历字  
符串，我们会在下面看到。

**(0)起始状态**  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP 0 0 0 0 0 0 0  
L 0 0 0 0 0 0 0  
R 0 0 0 0 0 0 0  
在这里，HLP存放的是节点指针，并且全都初始化为0，这里的L/R代表  
了该节点是否有左/右孩子。在下面注意HLP和MID的对应关系。  
**(1) \[A\]BCDEFG**  
我们查找A在MID中的位置，创建一个节点到对应位置，初创建的节  
点没有左右孩子。  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP 0 0 A 0 0 0 0  
L 0 0 0 0 0 0 0  
R 0 0 0 0 0 0 0  
**(2) A\[B\]CDEFG**  
 0 1 2 3 4 5 6  
MID D B A F E G C  
HLP 0 B A 0 0 0 0  
L 0 0 0 0 0 0 0  
R 0 0 0 0 0 0 0  
然后从B的左面开始找有没有非0的指针，在这里我们没有找到  
然后从B的右边开始找有没有非0的指针，找到了A  
发现A没有左孩子，令B为A的左孩子  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP 0 B A 0 0 0 0  
L 0 0 X 0 0 0 0  
R 0 0 0 0 0 0 0  
**(3) AB\[C\]DEFG**  
同上面步骤，发现C是A的右孩子  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP 0 B A 0 0 0 C  
L 0 0 X 0 0 0 0  
R 0 0 X 0 0 0 0  
**(4) ABC\[D\]EFG**  
同上，发现D是B的左孩子  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP D B A 0 0 0 C  
L 0 X X 0 0 0 0  
R 0 0 X 0 0 0 0  
**(5) ABCD\[E\]FG**  
这里有些不同，因为E向左找发现A的已经有了右孩子，所它必须向  
右找，结果发现E是C的左孩子  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP D B A 0 E 0 C  
L 0 X X 0 0 0 X  
R 0 0 X 0 0 0 0  
**(6) ABCDE\[F\]G**  
同上，F做不了A的右孩子，只能做了E的左孩子  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP D B A F E 0 C  
L 0 X X 0 X 0 X  
R 0 0 X 0 0 0 0  
**(7) ABCDEF\[G\]**  
G向左找，发现G可以做E的右孩子  
同上，F做不了A的右孩子，只能做了E的左孩子  
0 1 2 3 4 5 6  
MID D B A F E G C  
HLP D B A F E G C  
L 0 X X 0 X 0 X  
R 0 0 X 0 X 0 0

到此为止ABCDEFG的关系都已经建立好了，二叉树还原完成。  
至于为什么我们一定要先从左开始找，然后再向右找，也许是因为  
二叉树的中序遍历它本身就是从左到右的吧，具体没有深究过。  
这个算法同样适用于前序-中序，后序-中序的二叉树还原。但是  
使用这个算法你会发现需要申请与节点相同数量的临时空间，如果这  
个二叉树很大似乎会不太方便。而我的另外的前序-中序，后序-中序  
的二叉树还原算法所需要的临时空间的最大数目是二叉树的层次数。  
一个255个元素的满二叉树，层次为8，临时空间至多需要8，显然空间  
上比较优惠。  
不过话说回来，我所申请的空间最后都变成了二叉树，似乎也没有  
什么不妥。  
下面是算法C++表示

#include <iostream>
        #include <stack>
        #include <string>
        #include <queue>
        using namespace std;
        struct TreeNode {
            char       data;
            TreeNode*   lChild;
            TreeNode*   rChild;
        public:
            TreeNode(char c) : data(c), lChild(0), rChild(0) { }
        };
        //层次-中序二叉树还原 
        void Lev_Mid_Restore(string lev, string mid, TreeNode*& result) {
            const int size = lev.size();
            TreeNode* helper[size];
            for(int i = 0; i < size; i++)
                helper[i] = 0;
            /*            0  1  2  3  4  5  6  7  8
                helper    0  0  0  0  A  0  0  0  0
                lChild    0  0  0  0  0  0  0  0  0
                rChild    0  0  0  0  0  0  0  0  0
            */
            bool success = false;
            result = new TreeNode(lev[0]);
            int mi = mid.find(lev[0]);
            helper[mi] = result;
            
            for(int i = 1; i < lev.size(); i++) {
                success = false;
                mi = mid.find(lev[i]);
                helper[mi] = new TreeNode(lev[i]);  //把这个节点放到对应的数组位置中 
                /*从当前节点X的左边开始找，如果找到一个非0的节点Y，
                  就判断其右孩子是否为空，如果为空，则X是Y的右孩子，并且孩子配对成功，
                  接下来就不需要再向右找了。 
                  如果Y已经有右孩子了，则从节点X的右边开始找 
                */ 
                for(int p = mi - 1; p >= 0; p--) {
                    if(helper[p] != 0) {
                        if(helper[p]->rChild == 0) {
                            helper[p]->rChild = helper[mi];
                            success = true;
                        }
                        break;
                    }
                }
                if(success) {
                    continue;
                }
                /*从当前节点X的右边还是找，如果找到一个非0的节点Y
                  判断其左孩子是否为空，如果为空，则X是Y的左孩子
                  如果Y已经有左孩子了，则说明这个中序/层次遍历序列有问题
                */
                for(int p = mi + 1; p < size; p++) {
                    if(helper[p] != 0) {
                        if(helper[p]->lChild == 0) {
                            helper[p]->lChild = helper[mi];
                            success = true;
                        }
                        break;
                    }
                }
                //因为既然到了这一步，还没有配对成功，就说明给的中序/层次遍历序列
                //有问题 
                if(!success) {
                    cout << "error: " << lev[i] << endl;
                    break;
                }
            }
        }
        int main() {
            void inorderTraversal(TreeNode* pTree);
            void levelorderTraversal(TreeNode* pTree);
            void Lev_Mid_Restore(string lev, string mid, TreeNode*& result);
            /*                 A
                            /      /
                           B        C
                         /   /    /   /
                        D    E    F    G
                       / /  / /  / /  / /
                       H I  J K  M N  O P
            */
            string Levorder1 = "ABCDEFGHIJKMNOP";
            string Midorder1 = "HDIBJEKAMFNCOGP";
            
            string Levorder2 = "ABCDEFG";
            string Midorder2 = "BDAFEGC";
            TreeNode* res = 0;
            Lev_Mid_Restore(Levorder1, Midorder1, res);
            inorderTraversal(res);  
            levelorderTraversal(res);
            
            Lev_Mid_Restore(Levorder2, Midorder2, res);
            inorderTraversal(res);  
            levelorderTraversal(res);   
            
            cin.get();
        }
        //中序遍历 
        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;
        }
        //层次遍历 
        void levelorderTraversal(TreeNode* pTree) {
            queue<TreeNode*> treeQueue;
            treeQueue.push(pTree);
            while(!treeQueue.empty()) {
                cout << treeQueue.front()->data;
                TreeNode* lChild = treeQueue.front()->lChild;
                TreeNode* rChild = treeQueue.front()->rChild;
                if(lChild != 0) {
                    treeQueue.push(lChild);
                }
                if(rChild != 0) {
                    treeQueue.push(rChild);
                }
                treeQueue.pop();
            }
            cout << endl;
        }

[http_blog.csdn.net_matrixdwy_article_details_3111808]: http://blog.csdn.net/matrixdwy/article/details/3111808