主要内容 #

1. 二叉树的中序遍历
2. 实现代码

1. 二叉树的中序遍历 #

二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：

1. 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
2. 访问当前结点；
3. 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。

举个简单的例子，下图是一棵二叉树：

中序遍历这棵二叉树的过程是：

进入结点 A 的左子树，访问左子树中的结点；
    进入结点 B 的左子树，访问左子树中的结点；
        试图进入结点 D 的左子树，但该结点没有左子树；
        访问结点 D；
        试图进入结点 D 的右子树，但该结点没有右子树；
    访问结点 B；
    进入结点 B 的右子树，访问右子树中的结点；
        试图进入结点 E 的左子树，但该结点没有左子树；
        访问结点 E；
        试图进入结点 E 的右子树，但该结点没有右子树；
访问结点 A；
进入结点 A 的右子树，访问右子树中的结点；
    进入结点 C 的左子树，访问左子树中的结点；
        试图进入结点 F 的左子树，但该结点没有左子树；
        访问结点 F；
        试图进入结点 F 的右子树，但该结点没有右子树；
    访问结点 C；
    进入结点 C 的右子树，访问右子树中的结点；
        试图进入结点 G 的左子树，但该结点没有左子树；
        访问结点 G；
        试图进入结点 G 的右子树，但该结点没有右子树；

最终，中序遍历上图中的二叉树，访问各个结点的顺序是：
D B E A F C G

2. 实现代码 #

对于顺序表存储的二叉树，递归实现中序遍历的 C 语言程序为：

#include <stdio.h>
#define NODENUM 7
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];

//存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}

void INOrderTraverse(BiTree T, int p) {
    //递归遍历左子树
    if (((2 * p + 1) < NODENUM) && (T[2 * p + 1] != 0)) {
        INOrderTraverse(T, 2 * p + 1);
    }

    printf("%d ", T[p]);

    //递归遍历右子树
    if (((2 * p + 2) < NODENUM) && (T[2 * p + 2] != 0)){
        INOrderTraverse(T, 2 * p + 2);
    }  
}

int main() {
    BiTree T = { 0 };
    InitBiTree(T);

    INOrderTraverse(T, 0);

    return 0;
}
/*
执行结果为：
按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
4 2 5 1 6 3 7
*/

对于链表存储的二叉树，递归实现中序遍历的 C 语言程序为：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int

typedef struct BiTNode {
    TElemType data;//数据域
    struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;

void CreateBiTree(BiTree* T) {
    int num;
    scanf("%d", &num);
    //如果输入的值为 0，表示无此结点
    if (num == 0) {
        *T = NULL;
    }
    else
    {
        //创建新结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = num;
        CreateBiTree(&((*T)->lchild));//创建该结点的左孩子
        CreateBiTree(&((*T)->rchild));//创建该结点的右孩子
    }
}

//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}

void INOrderTraverse(BiTree T) {
    if (T) {
        INOrderTraverse(T->lchild);//遍历当前结点的左子树
        printf("%d ",T->data);     //访问当前结点
        INOrderTraverse(T->rchild);//遍历当前结点的右子树
    }
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    INOrderTraverse(Tree);
    DestroyBiTree(Tree);
    return 0;
}
/*
运行结果：
1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
4 2 5 1 6 3 7
*/