二叉树的前序遍历详解（图文并茂，C语言实现）

二叉树的前序遍历又叫先序遍历，指的是先访问根节点，然后先序遍历左子树，在左子树为空或已遍历时先序遍历右子树，即 DLR。
若二叉树为空（NULL），则什么也不做。

一棵二叉树的先序遍历过程如下：
1) 访问根 A，先序遍历 A 的左子树：


2) 访问根 B，先序遍历 B 的左子树：


3) 访问根 D，先序遍历 D 的左子树，D 的左子树为空，什么也不做，返回 D：


4) 先序遍历 D 的右子树，D 的右子树为空，返回 B：


5) 先序遍历 B 的右子树：


6) 访问根 E，先序遍历 E 的左子树，E 的左子树为空，返回 E。先序遍历 E 的右子树，E 的右子树为空，返回 A：


7) 先序遍历 A 的右子树：


8) 访问根 C，先序遍历 C 的左子树：


9) 访问根 F，先序遍历 F 的左子树，F 的左子树为空，返回 F：


10) 先序遍历 F 的右子树：


11) 访问根 G，先序遍历 G 的左子树，G 的左子树为空，返回 G。先序遍历 G 的右子树，G 的右子树为空，返回 C：


12) 先序遍历 C 的右子树，C 的右子树为空，遍历结束：


先序遍历序列为 A B D E C F G。

C语言实现先序遍历

实现先序遍历二叉树的关键代码如下：

void preorder(Btree T) { // 先序遍历
    if (T) {
        cout << T->data << " "; // 访问根节点
        preorder(T->lchild); // 递归遍历左子树
        preorder(T->rchild); // 递归遍历右子树
    }
}

实现先序遍历二叉树的完整代码如下：

#include <stdio.h>
#include <stdlib.h>

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

// 初始化树的函数
void CreateBiTree(BiTree *T) {
    *T = (BiTNode *)malloc(sizeof(BiTNode)); // 创建根节点A
    (*T)->data = 'A';
    (*T)->lchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建左子节点B
    (*T)->rchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建右子节点C

    (*T)->lchild->data = 'B';
    (*T)->lchild->lchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建B的左子节点D
    (*T)->lchild->rchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建B的右子节点E

    (*T)->rchild->data = 'C';
    (*T)->rchild->lchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建C的左子节点F
    (*T)->rchild->rchild = NULL; // C的右子节点为空

    (*T)->lchild->lchild->data = 'D';
    (*T)->lchild->lchild->lchild = NULL;
    (*T)->lchild->lchild->rchild = NULL;

    (*T)->lchild->rchild->data = 'E';
    (*T)->lchild->rchild->lchild = NULL;
    (*T)->lchild->rchild->rchild = NULL;

    (*T)->rchild->lchild->data = 'F';
    (*T)->rchild->lchild->lchild = NULL;
    (*T)->rchild->lchild->rchild = (BiTNode *)malloc(sizeof(BiTNode));// 创建F的右子节点G

    (*T)->rchild->lchild->rchild->data = 'G';
    (*T)->rchild->lchild->rchild->lchild = NULL;
    (*T)->rchild->lchild->rchild->rchild = NULL;
}

// 模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode *elem) {
    printf("%c ", elem->data);
}

// 先序遍历
void PreOrderTraverse(BiTree T) {
    if (T) {
        displayElem(T); // 调用操作结点数据的函数方法
        PreOrderTraverse(T->lchild); // 访问该结点的左孩子
        PreOrderTraverse(T->rchild); // 访问该结点的右孩子
    }
    // 如果结点为空，返回上一层
    return;
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍历: \n");
    PreOrderTraverse(Tree);
    return 0;
}

运行结果为：

先序遍历:
A B D E C F G