面试之---二叉树的遍历

二叉树的遍历根据对根的访问情况，分为三种

（1）前序遍历：根节点 --> 左孩子--> 右孩子

（2）中序遍历：左孩子 -- > 根节点 -- > 右孩子

（3）后序遍历：左孩子 --> 右孩子 --> 根节点

笔试中的题目，总是给出任意两个遍历，求出另外一个遍历；结题的思路：“找出根节点，划分左右两个区域，重复之”，下面按照题目分析：

【题目】
假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ，中序遍历序列为 DBGEHJACIF ，则其前序
遍历序列为 ( ) 。
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGHJFIC
D. ABDEGJHCFI

1.由后续遍历可得到根节点为A,可把中序遍历分为两个区 DBGEHJ 为A的左孩子区域， CIF为A的右孩子区域，左区域后续遍历的结果为DGJHEB,右区域后续遍历的结果为IFC

2.由第一步得到的左右两个区域的后续遍历序列，分别得到根节点的左右孩子为B, C;然后分别对左右两个区域按照步骤1，进行划分；

3.以A的做区域举例：后序遍历：DGJHEB 中序遍历：DBGEHJ.由后序遍历得到根节点为B,B的左区域只有一个节点D，为B的左孩子。B的右区域的中序遍历为GEHJ,后序遍历的结果为GJHE,因此E为B的右孩子节点。

按图索骥，可以得到前序遍历的结果为：ABDEGHJCFI;

付三种遍历算法的递归实现：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef char keytype;
typedef struct node
{
    keytype key;
    struct node * lchild;
    struct node * rchild;
}*pnode;
typedef struct node * tree;
pnode  initnode(keytype key)
{
    pnode pn;
    pn =(pnode)malloc(sizeof(pnode));
    pn->key = key;
    pn->lchild = NULL;
    pn->rchild = NULL;
    return pn;
}
pnode insert_lchid(pnode node, keytype key)
{
    pnode pn;
    pn = initnode(key);
    if (!pn)
    {
        printf("alloc node failed
");
        exit(-1);
    }
    node->lchild = pn;
    return pn;
}
pnode insert_rchid(pnode node, keytype key)
{
    pnode pn;
    pn = initnode(key);
    if (!pn)
    {
        printf("alloc node failed
");
        exit(-1);
    }
    node->rchild = pn;
    return pn;
}
tree inittree()
{
    tree ptree;
    pnode pparent, pchild;
    ptree = (tree)malloc(sizeof(tree));
    if (!ptree)
    {
        printf("alloc tree failed
");
        return NULL;
    }
    ptree = (tree)initnode('A');
    pparent = insert_lchid(ptree,'B');
    pchild = insert_lchid(pparent,'D');
    pchild = insert_rchid(pparent,'E');
    pparent = pchild;
    pchild = insert_lchid(pparent,'G');
    pchild = insert_rchid(pparent,'H');
    pparent = pchild;
    pchild = insert_lchid(pparent,'J');
    pparent = insert_rchid(ptree,'C');
    pparent = insert_rchid(pparent,'F');
    pparent = insert_lchid(pparent,'I');
    return ptree;
}
void visit(pnode pt)
{
    printf("%c,",pt->key);
}
void PreeOrderTrave(tree pt)
{
    if (pt)
    {
        visit((pnode)pt);
        PreeOrderTrave(pt->lchild);
        PreeOrderTrave(pt->rchild);
    }
}
void InorderTrave(tree pt)
{
    if (pt)
    {
        InorderTrave(pt->lchild);
        visit(pt);
        InorderTrave(pt->rchild);
    }


}
void lastorderTrave(tree pt)
{
    if (pt)
    {
        lastorderTrave(pt->lchild);
        lastorderTrave(pt->rchild);
        visit(pt);
    }


}
int main()
{
    tree pt;
    pt = inittree();
    printf("前序遍历：");
    PreeOrderTrave(pt);
    printf("
");
    printf("中序遍历：");
    InorderTrave(pt);
    printf("
");
    printf("后序遍历：");
    lastorderTrave(pt);
    printf("
");
        
}