二叉树四种遍历方式详解：前序、中序、后序与层序遍历

创作时间:

作者:

@小白创作中心

二叉树四种遍历方式详解：前序、中序、后序与层序遍历

引用

CSDN

https://blog.csdn.net/m0_65601072/article/details/124699065

二叉树的遍历是数据结构中的一个重要概念，它涉及到如何系统地访问二叉树中的所有节点。本文将详细介绍四种主要的二叉树遍历方式：前序遍历、中序遍历、后序遍历和层序遍历。每种遍历方式都有其独特的访问顺序和应用场景，通过本文的讲解和代码示例，读者将能够全面理解这些遍历方法的原理和实现。

前序遍历 (DLR) 递归算法

若二叉树为空，则算法结束；否则:

访问根结点
前序遍历根结点的左子树
前序遍历根结点的右子树

对于所示的二叉树，前序遍历访问结点的次序为:ABDGCEF

void PreOrder(BiTreeNode* root, void visit(DataType item)){
    //前序遍历二叉树root，访问操作为visit
    if (root != NULL)
    {
        visit(root->data);
        PreOrder(root->leftChild, visit);
        PreOrder(root->rightChild, visit);
    }
}

中序遍历 (LDR) 递归算法

若二叉树为空，则算法结束；否则:

中序遍历根结点的左子树
访问根结点
中序遍历根结点的右子树。

对于所示的二叉树，中序遍历访问结点的次序为:DGBAECF

void InOrder(BiTreeNode* root, void visit(DataType item)) {
    //中序遍历二叉树root，访问操作为visit
    if (root != NULL)
    {
        InOrder(root->leftChild, visit);
        visit(root->data);
        InOrder(root->rightChild, visit);
    }
}

后序遍历 (LRD) 递归算法

若二叉树为空，则算法结束; 否则:

后序遍历根结点的左子树
后序遍历根结点的右子树
访问根结点

对于所示的二叉树，后序遍历访问结点的次序为:GDBEFCA

void PostOrder(BiTreeNode* root, void visit(DataType item)) {
    //后序遍历二叉树root，访问操作为visit
    if (root != NULL)
    {
        PostOrder(root->leftChild, visit);
        PostOrder(root->rightChild, visit);
        visit(root->data);
    }
}

层序遍历队列实现方法

层序遍历的定义：

除前序、中序和后序遍历方法外，二叉树还有层序遍历方法。层序遍历方法的要求是:按二叉树的层序次序(即从根结点层至叶结点层），同一层中先按左子树再右子树的次序遍历二叉树。其实也很好理解，就是按二叉树从上到下，从左到右依次打印每个节点中存储的数据。

对于下图所示的二叉树，层序遍历访问结点的次序为: A B C D E F G

实现方法：

由分析可知，二叉树层序遍历方法的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此，可以借助队列实现二叉树的层序遍历。二叉树的层序遍历算法如下：

初始化设置一个队列。
把根结点指针入队列。
当队列非空时，循环执行步骤(a) 到步骤(c):

(a)出队列取得一个结点指针，访问该结点;
(b)若该结点的左子树非空，则将该结点的左孩子指针入队列;
(c)若该结点的右子树非空，则将该结点的右孩子指针入队列。

结束。

虽然二叉树是一种非线性结构，二叉树不能像单链表那样每个结点都有一个唯一的前驱结点和一个唯一的后继结点。但当对一颗二叉树用一种特定的遍历方法(如前序遍历方法、中序遍历方法等)进行遍历时，其遍历序列一定是线性的，且是唯一的。

代码实现

#include <stdio.h>
#include <stdlib.h>
#define QueueMax 100
typedef char DataType;
typedef struct Node
{//定义二叉树结点
    DataType data;
    struct Node* leftChild, * rightChild;
}BiTreeNode, * BiTree;
typedef struct
{//定义队列
    BiTree data[QueueMax];
    int head;
    int rear;
    int len;
}Queue;
BiTree CreateTree();  //建立二叉树
Queue InitQueue();  //初始化队列
int IsEmptyQueue(Queue seq);  //队列判空
int IsFullQueue(Queue seq);   //队列判满
void PushQueue(Queue* seq, BiTree T);  //入队
void PopQueue(Queue* seq, BiTree* T);  //出队
void LevelOrder(BiTree T);  //层序遍历
void PreOrder(BiTreeNode* root, void visit(DataType item));//前序遍历
void InOrder(BiTreeNode* root, void visit(DataType item));//中序遍历
void PostOrder(BiTreeNode* root, void visit(DataType item));//后序遍历
void visit(DataType item);//访问函数
//输入：ABD#G###CE##F##
//前序遍历：A B D G C E F
//中序遍历：D G B A E C F
//后序遍历：G D B E F C A
//层序遍历：A B C D E F G
int main()
{
    BiTree T = CreateTree();
    printf("前序遍历:");
    PreOrder(T, visit);//前序遍历
    printf("\n中序遍历:");
    InOrder(T, visit);//中序遍历
    printf("\n后序遍历:");
    PostOrder(T, visit);//后序遍历
    printf("\n层序遍历:");
    LevelOrder(T);//层序遍历
    return 0;
}
void visit(DataType item)
{
    printf("%c ", item);
}
BiTree CreateTree()
{  //建立二叉树
    char c = getchar();
    if (c == '#')  return NULL; 
     BiTree T = (BiTree)malloc(sizeof(BiTreeNode));
    T->data = c;
    T->leftChild = CreateTree();
    T->rightChild = CreateTree();
    return T;
}
void PreOrder(BiTreeNode* root, void visit(DataType item)) {
    //前序遍历二叉树root，访问操作为visit
    if (root != NULL)
    {
        visit(root->data);
        PreOrder(root->leftChild, visit);
        PreOrder(root->rightChild, visit);
    }
}
void InOrder(BiTreeNode* root, void visit(DataType item)) {
    //中序遍历二叉树root，访问操作为visit
    if (root != NULL)
    {
        InOrder(root->leftChild, visit);
        visit(root->data);
        InOrder(root->rightChild, visit);
    }
}
void PostOrder(BiTreeNode* root, void visit(DataType item)) {
    //后序遍历二叉树root，访问操作为visit
    if (root != NULL)
    {
        PostOrder(root->leftChild, visit);
        PostOrder(root->rightChild, visit);
        visit(root->data);
    }
}
Queue InitQueue()
{  //初始化队列
    Queue seq;
    for (int i = 0; i < QueueMax; i++)
    {
        seq.data[i] = NULL;
    }
    seq.head = 0;
    seq.rear = -1;
    seq.len = 0;
    return seq;
}
int IsEmptyQueue(Queue seq)
{  //队列判空
    if (seq.len == 0)  return 1; 
    return 0;
}
int IsFullQueue(Queue seq)
{  //队列判满
    if (seq.len == QueueMax)  return 1; 
    return 0;
}
void PushQueue(Queue* seq, BiTree T)
{  //入队
    if (IsFullQueue(*seq)) {
        printf("队列已满\n");
        return;
    }
    seq->rear = (seq->rear + 1) % QueueMax;
    seq->len++;
    seq->data[seq->rear] = T;
}
void PopQueue(Queue* seq, BiTree* T)
{  //出队
    if (IsEmptyQueue(*seq)) {
        printf("队列已空\n");
        return;
    }
    seq->head = (seq->head + 1) % QueueMax;
    *T = seq->data[seq->head];
    seq->len--;
}
void LevelOrder(BiTree T)
{  //层序遍历
    Queue seq = InitQueue();
    BiTree tmp = T;
    PushQueue(&seq, tmp);
    while (!IsEmptyQueue(seq)) 
    {
        printf("%c ", tmp->data);
        if (tmp->leftChild != NULL) 
        {
            PushQueue(&seq, tmp->leftChild);
        }
        if (tmp->rightChild != NULL) 
        {
            PushQueue(&seq, tmp->rightChild);
        }
        PopQueue(&seq, &tmp);
    }
}