主要内容 #

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

1. 二叉树的前序遍历 #

所谓前序或者先序遍历二叉树，指的是从根结点出发，按照以下步骤访问二叉树的每个结点：

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

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

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

访问根节点 A；
进入 A 的左子树，执行同样的步骤：
    访问结点 B；
    进入 B 的左子树，执行同样的步骤：
        访问结点 D；
        结点 D 没有左子树；
        结点 D 没有右子树；
    进入 B 的右子树，执行同样的步骤：
        访问结点 E；
        结点 E 没有左子树；
        结点 E 没有右子树；
进入 A 的右子树，执行同样的步骤：
    访问结点 C；
    进入 C 的左子树，执行同样的步骤：
        访问结点 F；
        结点 F 没有左子树；
        结点 F 没有右子树；
    进入 C 的右子树，执行同样的步骤：
        访问结点 G；
        结点 G 没有左子树；
        结点 G 没有右子树

经过以上过程，就访问了二叉树中的各个结点，访问的次序是：
A B D E C F 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 PreOrderTraverse(BiTree T, int p_node) {
    //根节点的值不为 0，证明二叉树存在
    if (T[p_node]) {
        printf("%d ", T[p_node]);
        //先序遍历左子树
        if ((2 * p_node + 1 < NODENUM) && (T[2 * p_node + 1] != 0)) {
            PreOrderTraverse(T, 2 * p_node + 1);
        }
        //最后先序遍历右子树
        if ((2 * p_node + 2 < NODENUM) && (T[2 * p_node + 2] != 0)) {
            PreOrderTraverse(T, 2 * p_node + 2);
        }
    }
}

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

    PreOrderTraverse(T,0);
    return 0;
}
/*
运行结果为：
按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7#
1 2 4 5 3 6 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 PreOrderTraverse(BiTree T) {
    //如果二叉树存在，则遍历二叉树
    if (T) {
        printf("%d ", T->data); //调用操作结点数据的函数方法
        PreOrderTraverse(T->lchild);//访问该结点的左孩子
        PreOrderTraverse(T->rchild);//访问该结点的右孩子
    }
}

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

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