二叉树中的先序遍历、中序遍历和后序遍历关系

我会带着你远行 2022-07-15 12:55 159阅读 0赞

先序、中序以及后序遍历是我们遍历二叉树常用方法，当然还有层级遍历。前三者属于深度优先遍历，后者属于广度优先遍历。今天我们谈谈前面三种遍历的关系。即，已知先序、中序、后序遍历中的哪几种可以确定一棵树的结构，从而得出另一种或两种遍历的结果。  
首先假设我们只知道三种遍历中的一种的结果。显然只知道一种遍历结果不能确定一棵树的结构，先序遍历和后序遍历只能找到根节点，不能判断左右子树；中序遍历甚至连根节点都找不到。  
那么假设我们知道三种遍历中的两种呢？假如我们知道了先序遍历和中序遍历的结果（树中所有节点元素的值两两都不相同），要求后序遍历的结果。做法是先找到先序遍历的第一个元素，它肯定是这棵树的根节点元素的值；然后到中序遍历结果中找这个值，那么中序遍历中这个值前面的所有元素都是根节点的左子树的节点的值，后面的所有元素都是根节点你的右子树的节点的值。现在我们对左右子树分别进行相同的操作，即递归调用当前的这个函数，就能构造出一棵完整的二叉树。  
同理的，假如我们已经知道了后序遍历和中序遍历的结果，一样能够用相同的方法还原这棵二叉树。  
但是，如果知道了先序遍历和后序遍历的结果，能不能还原这可二叉树呢？答案是不能。因为先序遍历和后序遍历本质上是一样的，先序遍历是先访问根节点再遍历左右子树，后序遍历是先遍历左右子树再访问根节点，因此我们即使知道了根节点也不能区分出左右子树。但是如果是中序遍历，我们知道了它的根节点就能知道它的左右子树，所以中序遍历在还原二叉树过程中是最重要的。不过仅仅知道中序遍历我们并不能知道哪个是它的根节点元素的值，所以还得通过先序遍历或者后序遍历来找到根节点。  
下面是我写的通过先序遍历和中序遍历结果还原二叉树的程序>\_<：

#include<iostream>
    using namespace std;
    
    template<typename T>
    struct TreeNode
    {
        T val;
        TreeNode* left, *right;
        TreeNode() :left(nullptr), right(nullptr) {}
        TreeNode(T v):val(v), left(nullptr), right(nullptr) {}
    };
    
    //思路:先序遍历的第一个元素肯定是根节点，那么我们再在中序遍历中找到这个根节点，此时中序遍历根节点左边的元素全是根节点左子树的元素，利用递归我们可以继续查找，直到构建一颗完整的树（这儿说的根节点都是指当前子树的根节点）
    template<typename T>
    void getTree(T* preOrderArr, T* inOrderArr,int end,TreeNode<T>*& node,TreeNode<T>*& finalRoot)
    {
        //node为当前节点，finalRoot为根节点，只有在为空时才会被赋值
        int start = 0;
        if (start > end)return;
        T rootValue = preOrderArr[start];
        int i;
        for (i= start; i <= end; ++i)
            if (inOrderArr[i] == rootValue)break;
        node = new TreeNode<T>(rootValue);
        if (finalRoot == nullptr)finalRoot = node;
        //为了防止根节点元素造成干扰，申请新的数组
        T* preLeftTree = new T[i - start];
        T* preRightTree = new T[end - i];
        T* inLeftTree = new T[i - start];
        T* inRightTree = new T[end - i];
        //copy的时候不将根节点元素copy进来
        for (int j = start + 1,count=0; j <= i; ++j,++count)
            preLeftTree[count] = preOrderArr[j];
        for (int j = i + 1, count = 0; j <= end; ++j, ++count)
            preRightTree[count] = preOrderArr[j];
        for (int j = start, count = 0; j <= i-1; ++j, ++count)
            inLeftTree[count] = inOrderArr[j];
        for (int j = i + 1, count = 0; j <= end; ++j, ++count)
            inRightTree[count] = inOrderArr[j];
        //通过递归的方法构造当前根节点的左右子树
        getTree(preLeftTree, inLeftTree, i-1, node->left,finalRoot);
        getTree(preRightTree, inRightTree, end-i-1, node->right,finalRoot);
    }
    
    //传入节点，输出以该节点为根的子树的后序遍历结果
    template<typename T>
    void postOrder(TreeNode<T>* node)
    {
        if (node)
        {
            postOrder(node->left);
            postOrder(node->right);
            cout << node->val << ' ';
        }
    }
    
    int main()
    {
        //测试1
        char pre[] = { 'a','b','d','e','h','c','f','g','i' };
        char in[] = { 'd','b','h','e','a','f','c','i','g' };
        //测试2
        char pre2[] = { 'a','b','d','f','h','j','l','c','e','g','i','k' };
        char in2[] = { 'l','j','h','f','d','b','a','c','e','g','i','k' };
    
        TreeNode<char>* root = nullptr;
        getTree(pre2, in2, 11, root, root);
        postOrder(root);
    
        system("pause");
    }