二叉树的前序，中序，后序遍历 的直观解释

时间：2022-12-24 11:26:08

首先我想先改变这几个遍历的名字（前根序遍历，中根序遍历，后根序遍历）；前中后本来就是相对于根结点来说的，少一个字会产生很多不必要的误解。

 

 二叉树的前序，中序，后序遍历 的直观解释

1. 前根序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。

ABDHECFG

2.中根序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。

HDBEAFCG

3.后根序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

HDEBFGCA

 

已知一棵二叉树的前根序序列和中根序序列，构造该二叉树的过程如下：
1. 根据前根序序列的第一个元素建立根结点；
2. 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
3. 在前根序序列中确定左右子树的前根序序列；
4. 由左子树的前根序序列和中根序序列建立左子树；
5. 由右子树的前根序序列和中根序序列建立右子树。

已知一棵二叉树的后根序序列和中根序序列，构造该二叉树的过程如下：
1. 根据后根序序列的最后一个元素建立根结点；
2. 在中根序序列中找到该元素，确定根结点的左右子树的中根序序列；
3. 在后根序序列中确定左右子树的后根序序列；
4. 由左子树的后根序序列和中根序序列建立左子树；
5. 由右子树的后根序序列和中根序序列建立右子树。


//由前序，中序序列，求后序序列

#include <bits/stdc++.h>

using namespace std;

struct Btree
{
    char data;
    struct Btree *lc,*rc;
};

char pre[10010];//前序序列
char mid[10010];//中序序列

struct Btree* creat(int len, char *pre, char *mid)//二叉树的重建
{
    struct Btree *root;
    int i ;
    if(len == 0)
    {
        return NULL;
    }
    root = new Btree;
    root -> data = pre[0];//找到根节点（前序遍历的第一位）
    for(i = 0; i < len; i++)//在中序序列中找到根节点的位置
    {
        if(mid[i] == pre[0])
            break;
    }

    root -> lc = creat(i, pre + 1, mid);//递归遍历（左子树的长度，左子树在pre中开始位置的地址，左子树在mid中开始位置的地址）
    root -> rc = creat(len-i-1, pre+i+1, mid+i+1);//（右子树的长度，右子树在pre中开始位置的地址，右子树在mid中开始位置的地址）

    return root;
};

void LRD(struct Btree *root)//后序遍历
{
    if(root)
    {
        LRD(root -> lc);
        LRD(root -> rc);
        cout<<root->data;
    }
}

int main()
{
    while(cin>>pre>>mid)
    {
        int len = strlen(pre);
        struct Btree *root;
        root = creat(len,pre,mid); 
        LRD(root);
        cout<<endl;
    }
    return 0;
}

//由中序，后序序列，求前序序列（套路完全一致）


#include <bits/stdc++.h>

using namespace std;

struct Btree
{
    char data;
    struct Btree *lc,*rc;
};

char mid[10010];//中序序列
char las[10010];//后序序列      

struct Btree* creat(int len, char *mid, char *las)//二叉树的重建
{
    struct Btree *root;
    int i ;
    if(len == 0)
    {
        return NULL;
    }
    root = new Btree;
    root -> data = las[len -1];//找到根节点（后序遍历的最后一位）
    for(i = 0; i < len; i++)//在中序序列中找到根节点的位置
    {
        if(mid[i] == las[len-1])
            break;
    }

    root -> lc = creat(i, mid, las);//递归遍历（左子树的长度，左子树在mid中开始位置的地址，左子树在las中开始位置的地址）
    root -> rc = creat(len-i-1, mid+i+1, las+i);//（右子树的长度，右子树在mid中开始位置的地址，右子树在las中开始位置的地址）

    return root;
};

void DLR(struct Btree *root)//前序遍历
{
    if(root)
    {
        cout<<root->data;
        DLR(root -> lc);
        DLR(root -> rc);
    }
}

int main()
{
    while(cin>>mid>>las)
    {
        int len = strlen(mid);
        struct Btree *root;
        root = creat(len,mid,las);
        DLR(root);
        cout<<endl;
    }
    return 0;
}


//可以说，在根据各种序列求另外的序列的时候，最关键的还是要找到，根节点在各个时刻在各个数列中的位置！！


标签：

相关文章