作者：解学武

建立一棵二叉树，并分别按先序、中序和后序遍历这棵二叉树，要求以二叉链表作为存储结构。

技术要点

创建二叉树的二叉链表，其基本思想为：首先对一般的二叉树添加若干个虚结点，使其每一个结点均有左右孩子，然后按先序遍历的顺序依次输入结点信息。

若输入的结点不是虚结点，则建立一个新结点，然后依次建立该结点的左孩子和右孩子；否则，新结点为空。
例如，建立如上图（a）所示的二叉树，其扩充二叉树如上图（b）所示，输入序列应为：A B D @ @ @ C E @ G @ @ F @ @ ，其中 @ 为虚结点。

构建好二叉树之后，在按照先序、中序和后序的遍历方式遍历二叉链表。

有关三种遍历方式的详细介绍，请阅读《二叉树的三种遍历方式》一文，本节不再过多讲述。

实现代码（附有详细注释）

#include <stdio.h>
#include <stdlib.h>
//结点结构体
typedef struct BiTNode{
    char data;//数据
    struct BiTNode * lchild,*rchild;//左右孩子指针
}BiTNode ,*BiTree;
//初始化二叉树的二叉链表T
void Create_BiTree(BiTree * T){
    char ch;
    ch = getchar();
    //@ 表示此处无结点，为虚结点
    if(ch == '@'){
        *T = NULL;
    }
    //# 表示构造结束
    else if(ch == '#'){
        return ;
    }
    //排除以上两种情况，则为有数据的结点，对其进行构造
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        //继续构造其左右孩子结点
        Create_BiTree(&(*T)->lchild);
        Create_BiTree(&(*T)->rchild);
    }
}
//先序遍历二叉树
void PreOrder(BiTree T){
    if(T){
        //遇到结点先输出其结点信息，然后按照先左后右的方式进行遍历
        printf("%3c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
//中序遍历二叉树
void InOrder(BiTree T){
    if(T){
        //中序遍历，即先遍历左孩子，然后输出结点数据，在遍历右孩子
        InOrder(T->lchild);
        printf("%3c",T->data);
        InOrder(T->rchild);
    }
}
//后序遍历二叉树
void PostOrder(BiTree T){
    if(T){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%3c",T->data);
    }
}
int main(){
    BiTree T;
    printf("input PreOrder str:");
    //构造二叉树
    Create_BiTree(&T);
    printf("\n");
    //分别按照先序、中序、后序的方式遍历二叉树
    printf("preorder list of  T :");
    PreOrder(T);
    printf("\nInOrder list of T :");
    InOrder(T);
    printf("\nPostOrder list of T:");
    PostOrder(T);
}

运行结果为：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。