前序遍历、中序遍历、后序遍历层序遍历详解附代码（数据结构C语言）

嘎嘎烤鸭

17128人浏览 · 2022-05-10 23:02:02

嘎嘎烤鸭 · 2022-05-10 23:02:02 发布

由于二叉树是递归定义的，显然，可以把二叉树遍历操作设计成递归算法。

从二叉树的定义可知，一棵二叉树由三部分组成:根结点，左子树和右子树。若规定D、L、R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，则共有6种组合: LDR、DLR、LRD、RDL、DRL和RLD,由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，因此我们只讨论6种组合的前三种: DLR、LDR和LRD,根据遍历方法对访问根结点处理的位置不同，称这三种遍历方法分别为前序遍历(DLR)、中序遍历(LDR)和后序遍历(LRD)方法

//定义一颗二叉树
typedef char DataType;
typedef struct Node {
	DataType data;
	struct Node* leftChild;
	struct Node* rightChild;
}BiTreeNode，*BiTree;

void visit(DataType item)
{
	printf("%c   ", item);
}

(1)前序遍历 (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);
	}
}

(2)中序遍历 (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);
	}
}

(3)后序遍历 (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);
	}
}

（4）层序遍历队列实现方法

层序遍历的定义：

除前序、中序和后序遍历方法外，二叉树还有层序遍历方法.。
层序遍历方法的要求是:按二叉树的层序次序(即从根结点层至叶结点层），同一层中先按左子树再右子树的次序遍历二叉树。

其实也很好理解，就是按二叉树从上到下，从左到右依次打印每个节点中存储的数据。

对于下图所示的二叉树，层序遍历访问结点的次序为: 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);
    }
}