十五、二叉树前序，中序，后序遍历详解

只要是搞计算机的，对数据结构中二叉树遍历都不陌生，但是如果用到的机会不多那么就会慢慢淡忘，温故而之新才是最好的学习方式，现在就重新温习一下这方面的知识。

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

image.png

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

ABDHECFG

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

HDBEAFCG

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

HDEBFGCA

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

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

根据前根序和中根序打印后根序代码：

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
 
char preArray[] = "ABDHECFG";
char midArray[] = "HDBEAFCG";
 
typedef struct BinaryTree BiTree;
struct BinaryTree 
{
    char data;
    BiTree *LTree,*RTree;
};
 
 
void CreateBTree(BiTree **node,int mid_header,int mid_tail,int pre_header,int pre_tail)
{
    
    if(pre_header <= pre_tail || mid_header <= mid_tail)
    {
        BiTree* child;
        child = (BiTree*)malloc(sizeof(BiTree));
        child->data = preArray[pre_header];
        child->LTree = NULL;
        child->RTree = NULL;
        *node = child;
        int mid_num;
        for (mid_num = 0;preArray[pre_header] != midArray[mid_num];mid_num++);
        CreateBTree(&child->LTree,mid_header,mid_num-1,pre_header+1,pre_header+mid_num-mid_header);//create left tree
        CreateBTree(&child->RTree,mid_num+1,mid_tail,pre_tail-mid_tail+mid_num+1,pre_tail);
    }
    else
    {
        *node=NULL;
    }
    
}
 
void ShowBTree(BiTree* p)
{
    if (p)
    {
        ShowBTree(p->LTree);
        ShowBTree(p->RTree);
        printf("%c",p->data);
    }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    
    BiTree *rootNode = NULL;
    rootNode = (BiTree*)malloc(sizeof(BiTree));
    rootNode->data = preArray[0];
    rootNode->LTree = NULL;
    rootNode->RTree = NULL;
    int mid_num = 0;
    for (mid_num = 0;preArray[0] != midArray[mid_num]; mid_num++);
    CreateBTree(&rootNode->LTree,0,mid_num-1,1,mid_num);//create left tree
    CreateBTree(&rootNode->RTree,mid_num+1,strlen(midArray)-1,mid_num+1,strlen(preArray)-1);//create right tree
    
    ShowBTree(rootNode);
    system("pause");
    return 0;
}