算法-重建二叉树

喜欢ヅ旅行 2022-06-10 06:10 140阅读 0赞

**题目：**  
输入某二叉树的前序遍历与中序遍历结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果均无重复数字，前序遍历序列为\{\}，中序遍历序列为\{\}，则重建出图2.6所示的二叉树并输出他的头结点。二叉树的结点定义如下：

struct BiTNode
    {  
        int data;  
        BiTNode* lchild;  
        BiTNode* rchild;  
    };

**解题思路：**

在[二叉树遍历总结][Link 1]中，我们介绍了常用的遍历方法，那么前序遍历序列的第一个点一定是根节点，又由于无重复数字，所以我们就知道了根结点在中序遍历中的位置：  
![这里写图片描述][SouthEast]  
又由于中序遍历的特点，根结点的左子结点一定是\{4,7,2\}，右子结点\{5,3,8,6\}。接下来我们再把左右子结点想象成一个单独的根结点，那么，他们又有了自己的根结点：  
![这里写图片描述][SouthEast 1]  
截止到这里，我们能确定位置的点就是1，2，3，以及它们的左右子结点（具体位置不清楚）：

![这里写图片描述][SouthEast 2]

下面的步骤就是，继续根据前序确定根结点，根据中序确定左右子结点，直到确定了所有的位置：

![这里写图片描述][SouthEast 3]

**代码实现：**  
上面说到，每一次确定一个根结点和对应的左右子结点，然后在把左右子结点想象单独的树，重复之前的步骤，显然这是个递归：

BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
    {
        if(preorder == NULL || inorder == NULL || length <= 0)
            return NULL;
    
        return ConstructCore(preorder, preorder + length - 1,
            inorder, inorder + length - 1);
    }
    
    BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
    {
        // 前序遍历序列的第一个数字是根结点的值
        int rootValue = startPreorder[0];
        BinaryTreeNode* root = new BinaryTreeNode();
        root->m_nValue = rootValue;
        root->m_pLeft = root->m_pRight = NULL;
    
        if(startPreorder == endPreorder)
        {
            if(startInorder == endInorder && *startPreorder == *startInorder)
                return root;
            else
                throw std::exception("Invalid input.");
        }
    
        // 在中序遍历中找到根结点的值
        int* rootInorder = startInorder;
        while(rootInorder <= endInorder && *rootInorder != rootValue)
            ++ rootInorder;
    
        if(rootInorder == endInorder && *rootInorder != rootValue)
            throw std::exception("Invalid input.");
    
        int leftLength = rootInorder - startInorder;
        int* leftPreorderEnd = startPreorder + leftLength;
        if(leftLength > 0)
        {
            // 构建左子树
            root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, 
                startInorder, rootInorder - 1);
        }
        if(leftLength < endPreorder - startPreorder)
        {
            // 构建右子树
            root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
                rootInorder + 1, endInorder);
        }
    
        return root;
    }

可以看到相比于链表，树相关的代码明显更多了，重建二叉树要50行左右。  
代码由两个函数组成，`Construct`函数的输入参数是int\*型，这是因为前序与中序遍历序列是int型的数组：

int preorder[length] = {
       1, 2, 4, 7, 3, 5, 6, 8};
     int inorder[length] = {
       4, 7, 2, 1, 5, 3, 8, 6};

重建的过程都在`ConstructCore`函数中，输入前序中序的开始于结束为止的地址，每一次都把前序序列的开始的地址作为新的树的根结点：

int rootValue = startPreorder[0];

递归退出的条件，就是前序序列开始的点与结束的点是一个。

[Link 1]: http://blog.csdn.net/chaipp0607/article/details/77050948
[SouthEast]: /images/20220610/ce41371f91c14bf2a9bbf18a9150ff9a.png
[SouthEast 1]: /images/20220610/eb5f80df2aa84c869442fd6fbfe133d4.png
[SouthEast 2]: /images/20220610/5d3c38aca31f4ac2a3deeb811f1ac97e.png
[SouthEast 3]: /images/20220610/aa2096841fae47c9b8208384256c88cc.png