二叉树遍历的转换C++实现

迷南。 2022-03-21 12:16 185阅读 0赞

二叉树的遍历分为以下三种：

*  先序遍历：遍历顺序规则为【根左右】
 *  中序遍历：遍历顺序规则为【左根右】
 *  后序遍历：遍历顺序规则为【左右根】

什么是【根左右】就是先遍历根，再遍历左节点，最后遍历右节点。  
举例来说：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70]

*  先序遍历：ABCDEFGHK
 *  中序遍历：BDCAEHGKF
 *  后序遍历：DCBHKGFEA

**在转换过程中要注意：**  
先序遍历根节点在首项  
中序遍历根节点在中间  
后序遍历根节点在最后  
因此在递归过程中根据中序根节点划分成两个部分。

**C++代码：**

#include <iostream>
    using namespace std;
     
    void ToPost(char *inOrder, char *preOrder, int length){
        if(length<=0)return;
        int root;
        for(root=0;root<length;root++){
            if(inOrder[root]==preOrder[0])break;
        }
        ToPost(inOrder,preOrder+1,root);
        ToPost(inOrder+root+1,preOrder+root+1,length-root-1);
        cout<<preOrder[0];
    }
     
    void ToPre(char *inOrder, char *postOrder, int length){
        if(length<=0)return;
        int root;
        for(root=0;root<length;root++){
            if(inOrder[root]==postOrder[length-1])break;
        }
        cout<<postOrder[length-1];
        ToPre(inOrder,postOrder,root);
        ToPre(inOrder+root+1,postOrder+root,length-root-1);
    }
     
    int main()
    {
        char pre[]="ABDECFG";
        char in[]="DBEAFCG";
        char post[]="DEBFGCA";
        cout<<"原始序列:\n";
        cout<<"Pre:"<<pre<<endl
            <<"In:"<<in<<endl
            <<"Post:"<<post<<endl;
     
        cout<<"后序遍历:\n";
        ToPost(in,pre,8);
        cout<<endl;
        cout<<"前序遍历:\n";
        ToPre(in,post,8);
        cout<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70]: /images/20220321/1a6feb7f36ee40d4b54fdcb9055ce91e.png
[omegaxyz.com]: http://xn--omegaxyz-on6m893d6sgwn0bu73h213a.com