帶你一文看懂二叉樹的先（中、后）序遍歷以及層次遍歷（圖解+遞歸/非遞歸代碼實(shí)現(xiàn)）

頭號碼甲 2022-05-16 發(fā)布于北京

展開全文

先序遍歷規(guī)則

??先序遍歷的核心思想：1.訪問根節(jié)點(diǎn)；2.訪問當(dāng)前節(jié)點(diǎn)的左子樹；3.若當(dāng)前節(jié)點(diǎn)無左子樹，則訪問當(dāng)前節(jié)點(diǎn)的右子樹；即考察到一個節(jié)點(diǎn)后，即刻輸出該節(jié)點(diǎn)的值，并繼續(xù)遍歷其左右子樹。(根左右)

先序遍歷舉例

??如圖所示，采用先序遍歷訪問這顆二叉樹的詳細(xì)過程為：
??1.訪問該二叉樹的根節(jié)點(diǎn)，找到 1；
??2.訪問節(jié)點(diǎn) 1 的左子樹，找到節(jié)點(diǎn) 2；
??3.訪問節(jié)點(diǎn) 2 的左子樹，找到節(jié)點(diǎn) 4；
??4.由于訪問節(jié)點(diǎn) 4 左子樹失敗，且也沒有右子樹，因此以節(jié)點(diǎn) 4 為根節(jié)點(diǎn)的子樹遍歷完成。但節(jié)點(diǎn) 2 還沒有遍歷其右子樹，因此現(xiàn)在開始遍歷，即訪問節(jié)點(diǎn) 5；
??5.由于節(jié)點(diǎn) 5 無左右子樹，因此節(jié)點(diǎn) 5 遍歷完成，并且由此以節(jié)點(diǎn) 2 為根節(jié)點(diǎn)的子樹也遍歷完成。現(xiàn)在回到節(jié)點(diǎn) 1 ，并開始遍歷該節(jié)點(diǎn)的右子樹，即訪問節(jié)點(diǎn) 3；
??6.訪問節(jié)點(diǎn) 3 左子樹，找到節(jié)點(diǎn) 6；
??7.由于節(jié)點(diǎn) 6 無左右子樹，因此節(jié)點(diǎn) 6 遍歷完成，回到節(jié)點(diǎn) 3 并遍歷其右子樹，找到節(jié)點(diǎn) 7；
??8.節(jié)點(diǎn) 7 無左右子樹，因此以節(jié)點(diǎn) 3 為根節(jié)點(diǎn)的子樹遍歷完成，同時回歸節(jié)點(diǎn) 1。由于節(jié)點(diǎn) 1 的左右子樹全部遍歷完成，因此整個二叉樹遍歷完成；
??因此，圖中二叉樹采用先序遍歷得到的序列為：1 2 4 5 3 6 7
在這里插入圖片描述

先序遍歷代碼（遞歸）

/*
 * @Description: 
 * @Version: 
 * @Autor: Carlos
 * @Date: 2020-05-29 16:55:41
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:03:23
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    TElemType data;//數(shù)據(jù)域
    struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;

/**
 * @Description: 初始化樹的函數(shù)
 * @Param: BiTree *T 結(jié)構(gòu)體指針的指針
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    //根節(jié)點(diǎn)
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    //1節(jié)點(diǎn)的左孩子2
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //2節(jié)點(diǎn)的右孩子5
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    //1節(jié)點(diǎn)的右孩子3
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    //3節(jié)點(diǎn)的左孩子6
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //3節(jié)點(diǎn)的右孩子7
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    //2節(jié)點(diǎn)的左孩子4
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}


/**
 * @Description: 模擬操作結(jié)點(diǎn)元素的函數(shù)，輸出結(jié)點(diǎn)本身的數(shù)值
 * @Param:BiTree elem 就結(jié)構(gòu)體指針
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}

/**
 * @Description: 先序遍歷
 * @Param: BiTree T 結(jié)構(gòu)體指針
 * @Return: 無
 * @Author: Carlos
 */
void PreOrderTraverse(BiTree T){
    if (T) {
        PrintBiT(T);//調(diào)用操作結(jié)點(diǎn)數(shù)據(jù)的函數(shù)方法
        PreOrderTraverse(T->lchild);//訪問該結(jié)點(diǎn)的左孩子
        PreOrderTraverse(T->rchild);//訪問該結(jié)點(diǎn)的右孩子
    }
    //如果結(jié)點(diǎn)為空，返回上一層
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍歷: \n");
    PreOrderTraverse(Tree);
}

先序遍歷代碼（非遞歸）

??因?yàn)橐诒闅v完某個樹的根節(jié)點(diǎn)的左子樹后接著遍歷節(jié)點(diǎn)的右子樹，為了能找到該樹的根節(jié)點(diǎn)，需要使用棧來進(jìn)行暫存。中序和后序也都涉及到回溯，所以都需要用到棧。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    TElemType data;//數(shù)據(jù)域
    struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
int top = -1;
//定義一個順序棧
BiTree  a[20];
/**
 * @Description: 初始化樹
 * @Param: BiTree *T 指針的指針
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    //根節(jié)點(diǎn)
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    //1節(jié)點(diǎn)的左孩子2
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //2節(jié)點(diǎn)的右孩子5
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    //1節(jié)點(diǎn)的右孩子3
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    //3節(jié)點(diǎn)的左孩子6
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //3節(jié)點(diǎn)的右孩子7
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    //2節(jié)點(diǎn)的左孩子4
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 打印二叉樹
 * @Param: BiTree elem 指針的指針
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 二叉樹壓棧函數(shù)
 * @Param: BiTree* a 結(jié)構(gòu)體指針的指針（也可以理解為指針數(shù)組） BiTree elem 結(jié)構(gòu)體指針
 * @Return: 無
 * @Author: Carlos
 */
void Push(BiTree* a,BiTree elem)
{
     a[++top]=elem;
}
/**
 * @Description: 二叉樹彈棧函數(shù)
 * @Param: 無
 * @Return: 無
 * @Author: Carlos
 */
void Pop()
{
    if (top==-1) {
        return ;
    }
    top--;
}
/**
 * @Description: 獲取棧頂元素
 * @Param: BiTree*a 結(jié)構(gòu)體指針數(shù)組
 * @Return: 結(jié)構(gòu)體指針
 * @Author: Carlos
 */
BiTree GetTop(BiTree*a){
    return a[top];
}
/**
 * @Description: 先序遍歷
 * @Param: BiTree Tree 結(jié)構(gòu)體指針
 * @Return: 無
 * @Author: Carlos
 */
void PreOrderTraverse(BiTree Tree)
{
   //臨時指針
    BiTree p;
    //根結(jié)點(diǎn)進(jìn)棧
    Push(a, Tree);
    while (top!=-1) {
        //取棧頂元素
        p=GetTop(a);
        //彈棧
        Pop();
        while (p) {
            //調(diào)用結(jié)點(diǎn)的操作函數(shù)
            PrintBiT(p);
            //如果該結(jié)點(diǎn)有右孩子，右孩子進(jìn)棧
            if (p->rchild) {
                Push(a,p->rchild);
            }
            p=p->lchild;//一直指向根結(jié)點(diǎn)最后一個左孩子
        }
    }
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍歷: \n");
    PreOrderTraverse(Tree);
    
}

中序遍歷

中序遍歷規(guī)則

??二叉樹中序遍歷的實(shí)現(xiàn)思想是：1.訪問當(dāng)前節(jié)點(diǎn)的左子樹；2.訪問根節(jié)點(diǎn)；3.訪問當(dāng)前節(jié)點(diǎn)的右子樹。即考察到一個節(jié)點(diǎn)后，將其暫存，遍歷完左子樹后，再輸出該節(jié)點(diǎn)的值，然后遍歷右子樹。(左根右)

中序遍歷舉例

在這里插入圖片描述
??以上圖為例，采用中序遍歷的思想遍歷該二叉樹的過程為：
??1.訪問該二叉樹的根節(jié)點(diǎn)，找到 1；
??2.遍歷節(jié)點(diǎn) 1 的左子樹，找到節(jié)點(diǎn) 2；
??3.遍歷節(jié)點(diǎn) 2 的左子樹，找到節(jié)點(diǎn) 4；
??4.由于節(jié)點(diǎn) 4 無左孩子，因此找到節(jié)點(diǎn) 4，并遍歷節(jié)點(diǎn) 4 的右子樹；
??5.由于節(jié)點(diǎn) 4 無右子樹，因此節(jié)點(diǎn) 2 的左子樹遍歷完成，訪問節(jié)點(diǎn) 2；
??6.遍歷節(jié)點(diǎn) 2 的右子樹，找到節(jié)點(diǎn) 5；
??7.由于節(jié)點(diǎn) 5 無左子樹，因此訪問節(jié)點(diǎn) 5 ，又因?yàn)楣?jié)點(diǎn) 5 沒有右子樹，因此節(jié)點(diǎn) 1 的左子樹遍歷完成，訪問節(jié)點(diǎn) 1 ，并遍歷節(jié)點(diǎn) 1 的右子樹，找到節(jié)點(diǎn) 3；
??8.遍歷節(jié)點(diǎn) 3 的左子樹，找到節(jié)點(diǎn) 6；
??9.由于節(jié)點(diǎn) 6 無左子樹，因此訪問節(jié)點(diǎn) 6，又因?yàn)樵摴?jié)點(diǎn)無右子樹，因此節(jié)點(diǎn) 3 的左子樹遍歷完成，開始訪問節(jié)點(diǎn) 3 ，并遍歷節(jié)點(diǎn) 3 的右子樹，找到節(jié)點(diǎn) 7；
??10.由于節(jié)點(diǎn) 7 無左子樹，因此訪問節(jié)點(diǎn) 7，又因?yàn)樵摴?jié)點(diǎn)無右子樹，因此節(jié)點(diǎn) 1 的右子樹遍歷完成，即整棵樹遍歷完成；
??因此，上圖中二叉樹采用中序遍歷得到的序列為：4 2 5 1 6 3 7

中序遍歷代碼（遞歸）

/*
 * @Description: 遞歸實(shí)現(xiàn)的中序遍歷
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-18 14:53:29
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:21:06
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    //數(shù)據(jù)域
    TElemType data;
    //左右孩子指針
    struct BiTreelchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化樹
 * @Param: BiTree *T  結(jié)構(gòu)體指針的指針（指針數(shù)組）
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 顯示函數(shù)
 * @Param: BiTree elem 結(jié)構(gòu)體指針
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 中序遍歷
 * @Param: BiTree T 結(jié)構(gòu)體指針
 * @Return: 無
 * @Author: Carlos
 */
void INOrderTraverse(BiTree T){
    if (T) {
        INOrderTraverse(T->lchild);//遍歷左孩子
        PrintBiT(T);//調(diào)用操作結(jié)點(diǎn)數(shù)據(jù)的函數(shù)方法
        INOrderTraverse(T->rchild);//遍歷右孩子
    }
    //如果結(jié)點(diǎn)為空，返回上一層
    return;
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("中序遍歷算法: \n");
    INOrderTraverse(Tree);
}

中序遍歷代碼（非遞歸）

??和非遞歸先序遍歷類似，唯一區(qū)別是考查到當(dāng)前節(jié)點(diǎn)時，并不直接輸出該節(jié)點(diǎn)。而是當(dāng)考查節(jié)點(diǎn)為空時，從棧中彈出的時候再進(jìn)行輸出(永遠(yuǎn)先考慮左子樹，直到左子樹為空才訪問根節(jié)點(diǎn))。

/*
 * @Description: 二叉樹的先序遍歷（非遞歸）
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-17 16:35:27
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-18 14:51:01
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DBG_PRINTF(fmt, args...)  do{    printf("<<File:%s  Line:%d  Function:%s>> ", __FILE__, __LINE__, __FUNCTION__);    printf(fmt, ##args);}while(0)
#define TElemType int
int top=-1;//top變量時刻表示棧頂元素所在位置
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    //數(shù)據(jù)域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化樹
 * @Param: BiTree *T  結(jié)構(gòu)體指針的指針
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 中序遍歷使用的進(jìn)棧函數(shù)
 * @Param: BiTree* a 指向樹的指針數(shù)組 BiTree elem 進(jìn)棧的元素
 * @Return: 無
 * @Author: Carlos
 */
void Push(BiTree* a,BiTree elem){
    //指針進(jìn)棧
    a[++top]=elem;
}
/**
 * @Description: 前序遍歷使用的彈棧函數(shù)
 * @Param: 無
 * @Return: 無
 * @Author: Carlos
 */
void Pop( ){
    if (top==-1) {
        return;
    }
    top--;
}
/**
 * @Description: 顯示函數(shù)
 * @Param: BiTree elem 指向樹的指針
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 拿到棧頂元素
 * @Param: BiTree*a 指針數(shù)組
 * @Return: 棧頂元素的地址
 * @Author: Carlos
 */
BiTree GetTop(BiTree*a){
    return a[top];
}
/**
 * @Description: 中序遍歷非遞歸算法，先左，然后回退，然后右。從根結(jié)點(diǎn)開始，遍歷左孩子同時壓棧，當(dāng)遍歷結(jié)束，說明當(dāng)前遍歷的結(jié)點(diǎn)沒有左孩子，
 * 從棧中取出來調(diào)用操作函數(shù)，然后訪問該結(jié)點(diǎn)的右孩子，繼續(xù)以上重復(fù)性的操作
 * @Return: 棧頂元素的地址
 * @Author: Carlos
 */
void InOrderTraverse1(BiTree Tree){
    //定義一個順序棧
    BiTree a[20];
    //臨時指針
    BiTree p;
    //根結(jié)點(diǎn)進(jìn)棧
    Push(a, Tree);
    //top!=-1說明棧內(nèi)不為空，程序繼續(xù)運(yùn)行
    while (top!=-1) {
        //一直取棧頂元素，且不能為NULL
        while ((p=GetTop(a)) &&p){
            //將該結(jié)點(diǎn)的左孩子進(jìn)棧，如果沒有左孩子，NULL進(jìn)棧
            Push(a, p->lchild);
        }
        //跳出循環(huán)，棧頂元素肯定為NULL，將NULL彈棧。 打印的第一個元素沒有右孩子，所以也會Pop掉，再取棧頂元素就是第一個元素的父節(jié)點(diǎn)
        Pop();
        if (top!=-1) {
            //取棧頂元素
            p=GetTop(a);
            //棧頂元素彈棧
            Pop();
            //遍歷完所有左孩子之后，打印棧頂?shù)脑亍?            PrintBiT(p);
            //將p指向的結(jié)點(diǎn)的右孩子進(jìn)棧
            Push(a, p->rchild);
        }
    }
}
/**
 * @Description: 中序遍歷非遞歸算法。中序遍歷過程中，只需將每個結(jié)點(diǎn)的左子樹壓棧即可，右子樹不需要壓棧。
 * 當(dāng)結(jié)點(diǎn)的左子樹遍歷完成后，只需要以棧頂結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)，繼續(xù)循環(huán)遍歷即可
 * @Param: 無
 * @Return: 棧頂元素的地址
 * @Author: Carlos
 */
void InOrderTraverse2(BiTree Tree){
    //定義一個順序棧
    BiTree a[20];
    //臨時指針
    BiTree p;
    p=Tree;
    //當(dāng)p為NULL或者棧為空時，表明樹遍歷完成
    while (p || top!=-1) {
        //如果p不為NULL，將其壓棧并遍歷其左子樹
        if (p) {
            Push(a, p);
            p=p->lchild;
        }
        //如果p==NULL，表明左子樹遍歷完成，需要遍歷上一層結(jié)點(diǎn)的右子樹  彈出時順便訪問右子樹
        else{
            p=GetTop(a);
            Pop();
            PrintBiT(p);
            p=p->rchild;
        }
    }
}
int main(){
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("中序遍歷: \r\n");
    InOrderTraverse2(Tree);
    DBG_PRINTF("123456\r\n");
    return 0;
}

后序遍歷

后序遍歷規(guī)則

??二叉樹后序遍歷的實(shí)現(xiàn)思想是：1.訪問左子樹；2.訪問右子樹；3.完成該節(jié)點(diǎn)的左右子樹的訪問后，再訪問該節(jié)點(diǎn)。即考察到一個節(jié)點(diǎn)后，將其暫存，遍歷完左右子樹后，再輸出該節(jié)點(diǎn)的值。(左右根)

后序遍歷舉例

在這里插入圖片描述
??如上圖中，對此二叉樹進(jìn)行后序遍歷的操作過程為：
??從根節(jié)點(diǎn) 1 開始，遍歷該節(jié)點(diǎn)的左子樹（以節(jié)點(diǎn) 2 為根節(jié)點(diǎn)）；
??1.遍歷節(jié)點(diǎn) 2 的左子樹（以節(jié)點(diǎn) 4 為根節(jié)點(diǎn)）；
??2.由于節(jié)點(diǎn) 4 既沒有左子樹，也沒有右子樹，此時訪問該節(jié)點(diǎn)中的元素 4，并回退到節(jié)點(diǎn) 2 ，遍歷節(jié)點(diǎn) 2 的右子樹（以 5 為根節(jié)點(diǎn)）；
??3.由于節(jié)點(diǎn) 5 無左右子樹，因此可以訪問節(jié)點(diǎn) 5 ，并且此時節(jié)點(diǎn) 2 的左右子樹也遍歷完成，因此也可以訪問節(jié)點(diǎn) 2；
??4.此時回退到節(jié)點(diǎn) 1 ，開始遍歷節(jié)點(diǎn) 1 的右子樹（以節(jié)點(diǎn) 3 為根節(jié)點(diǎn)）；
??5.遍歷節(jié)點(diǎn) 3 的左子樹（以節(jié)點(diǎn) 6 為根節(jié)點(diǎn)）；
??6.由于節(jié)點(diǎn) 6 無左右子樹，因此訪問節(jié)點(diǎn) 6，并回退到節(jié)點(diǎn) 3，開始遍歷節(jié)點(diǎn) 3 的右子樹（以節(jié)點(diǎn) 7 為根節(jié)點(diǎn)）；
??7.由于節(jié)點(diǎn) 7 無左右子樹，因此訪問節(jié)點(diǎn) 7，并且節(jié)點(diǎn) 3 的左右子樹也遍歷完成，可以訪問節(jié)點(diǎn) 3；節(jié)點(diǎn) 1 的左右子樹也遍歷完成，可以訪問節(jié)點(diǎn) 1；
??由此，對上圖中二叉樹進(jìn)行后序遍歷的結(jié)果為：4 5 2 6 7 3 1

后序遍歷代碼（遞歸）

/*
 * @Description: 二叉樹的后序遍歷（遞歸）
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-18 16:23:57
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:29:38
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    //數(shù)據(jù)域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
* @Description: 初始化樹
* @Param: BiTree *T  結(jié)構(gòu)體指針
* @Return: 無
* @Author: Carlos
*/
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));

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

    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;

    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

/**
* @Description: 顯示函數(shù)
* @Param: BiTree elem 指向樹的結(jié)構(gòu)體指針
* @Return: 無
* @Author: Carlos
*/
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
* @Description: 先序遍歷
* @Param: BiTree T 指針數(shù)組，存放各個節(jié)點(diǎn)的指針
* @Return: 無
* @Author: Carlos
*/
void PreOrderTraverse(BiTree T){
    if (T) {
        PreOrderTraverse(T->lchild);//訪問該結(jié)點(diǎn)的左孩子
        PreOrderTraverse(T->rchild);//訪問該結(jié)點(diǎn)的右孩子
         PrintBiT(T);//調(diào)用操作結(jié)點(diǎn)數(shù)據(jù)的函數(shù)方法
    }
    //如果結(jié)點(diǎn)為空，返回上一層
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍歷: \n");
    PreOrderTraverse(Tree);
}

后序遍歷代碼（非遞歸）

/*
 * @Description: 二叉樹的后序遍歷（非遞歸）
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-18 16:23:57
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-18 16:24:29
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//top變量時刻表示棧頂元素所在位置
int top=-1;
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    //數(shù)據(jù)域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化樹
 * @Param: BiTree *T  結(jié)構(gòu)體指針數(shù)組
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 后序遍歷使用的彈棧函數(shù)
 * @Param: 無
 * @Return: 無
 * @Author: Carlos
 */
void Pop( ){
    if (top==-1) {
        return ;
    }
    top--;
}
/**
 * @Description: 顯示函數(shù)
 * @Param: 無
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}

//增加左右子樹的訪問標(biāo)志
typedef struct SNode{
    BiTree p;
    int tag;
}SNode;
/**
 * @Description: 后序遍歷使用的進(jìn)棧函數(shù)
 * @Param: SNode *a 指向樹和標(biāo)志位的結(jié)構(gòu)體的指針 BiTree sdata 進(jìn)棧的元素
 * @Return: 無
 * @Author: Carlos
 */
void Push(SNode *a,SNode sdata){
    a[++top]=sdata;
}
/**
 * @Description: 后序遍歷非遞歸算法。后序遍歷是在遍歷完當(dāng)前結(jié)點(diǎn)的左右孩子之后，才調(diào)用操作函數(shù)，所以需要在操作結(jié)點(diǎn)進(jìn)棧時，為每個結(jié)點(diǎn)配備一個標(biāo)志位。
 * 當(dāng)遍歷該結(jié)點(diǎn)的左孩子時，設(shè)置當(dāng)前結(jié)點(diǎn)的標(biāo)志位為 0，進(jìn)棧；當(dāng)要遍歷該結(jié)點(diǎn)的右孩子時，設(shè)置當(dāng)前結(jié)點(diǎn)的標(biāo)志位為 1，進(jìn)棧。這樣，當(dāng)遍歷完成，該結(jié)點(diǎn)彈棧時，
 * 查看該結(jié)點(diǎn)的標(biāo)志位的值：如果是 0，表示該結(jié)點(diǎn)的右孩子還沒有遍歷；反之如果是 1，說明該結(jié)點(diǎn)的左右孩子都遍歷完成，可以調(diào)用操作函數(shù)。
 * @Param: 結(jié)構(gòu)體指針數(shù)組
 * @Return: 無
 * @Author: Carlos
 */
void PostOrderTraverse(BiTree Tree){
    //定義一個順序棧
    SNode a[20];
    //臨時指針
    BiTree p;
    int tag;
    SNode sdata;
    p=Tree;
    while (p||top!=-1) {
        //左孩子進(jìn)棧
        while (p) {
            //為該結(jié)點(diǎn)入棧做準(zhǔn)備
            sdata.p=p;
            //由于遍歷是左孩子，設(shè)置標(biāo)志位為0
            sdata.tag=0;
            //壓棧
            Push(a, sdata);
            //以該結(jié)點(diǎn)為根結(jié)點(diǎn)，遍歷左孩子
            p=p->lchild;
        }
        //取棧頂元素 取左孩子的父節(jié)點(diǎn)
        sdata=a[top];
        //棧頂元素彈棧
        Pop();
        p=sdata.p;
        tag=sdata.tag;
        //右孩子進(jìn)棧
        //如果tag==0，說明該結(jié)點(diǎn)還沒有遍歷它的右孩子
        if (tag==0) {
            sdata.p=p;
            sdata.tag=1;
            //更改該結(jié)點(diǎn)的標(biāo)志位，重新壓棧
            Push(a, sdata);
            //以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)，重復(fù)循環(huán)
            p=p->rchild;
        }
        //如果取出來的棧頂元素的tag==1，說明此結(jié)點(diǎn)左右子樹都遍歷完了，可以調(diào)用操作函數(shù)了
        else{
            PrintBiT(p);
            p=NULL;
        }
    }
}
int main(){
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍歷: \n");
    PostOrderTraverse(Tree);
}

層次遍歷

層次遍歷規(guī)則

??按照二叉樹中的層次從左到右依次遍歷每層中的結(jié)點(diǎn)。通過使用隊列的數(shù)據(jù)結(jié)構(gòu)，從樹的根結(jié)點(diǎn)開始，依次將其左孩子和右孩子入隊。而后每次隊列中一個結(jié)點(diǎn)出隊，都將其左孩子和右孩子入隊，直到樹中所有結(jié)點(diǎn)都出隊，出隊結(jié)點(diǎn)的先后順序就是層次遍歷的最終結(jié)果。

層次遍歷舉例

在這里插入圖片描述
??例如，層次遍歷如上圖中的二叉樹：
??1.根結(jié)點(diǎn) 1 入隊；
??2.根結(jié)點(diǎn) 1 出隊，出隊的同時，將左孩子 2 和右孩子 3 分別入隊；
??3.隊頭結(jié)點(diǎn) 2 出隊，出隊的同時，將結(jié)點(diǎn) 2 的左孩子 4 和右孩子 5 依次入隊；
??4.隊頭結(jié)點(diǎn) 3 出隊，出隊的同時，將結(jié)點(diǎn) 3 的左孩子 6 和右孩子 7 依次入隊；
??5.不斷地循環(huán)，直至隊列內(nèi)為空。

層次遍歷代碼

/*
 * @Description: 二叉樹的層次遍歷
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-20 14:52:38
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:41:48
 */ 
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
//初始化隊頭和隊尾指針開始時都為0
int front=0,rear=0;
typedef struct BiTNode{
    //數(shù)據(jù)域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//采用順序隊列，初始化創(chuàng)建隊列數(shù)組
BiTree a[20];
/**
 * @Description: 初始化二叉樹
 * @Param: BiTree *T 二叉樹的結(jié)構(gòu)體指針數(shù)組
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
   
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
   
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
   
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
   
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 入隊
 * @Param: BiTree *a 二叉樹結(jié)構(gòu)體指針  BiTree node 入隊的節(jié)點(diǎn)
 * @Return: 無
 * @Author: Carlos
 */
void EnQueue(BiTree *a,BiTree node){
    a[rear++]=node;
}
/**
 * @Description: 出隊
 * @Param: BiTree *node 二叉樹結(jié)構(gòu)體指針數(shù)組
 * @Return: 結(jié)構(gòu)體指針
 * @Author: Carlos
 */
BiTree DeQueue(BiTree *node){
    return a[front++];
}
/**
 * @Description: 二叉樹輸出函數(shù)
 * @Param: BiTree node 輸出的節(jié)點(diǎn)
 * @Return: 無
 * @Author: Carlos
 */
void displayNode(BiTree node){
    printf("%d ",node->data);
}
int main() {
    BiTree tree;
    //初始化二叉樹
    CreateBiTree(&tree);
    BiTree p;

    //根結(jié)點(diǎn)入隊
    EnQueue(a, tree);
    //當(dāng)隊頭和隊尾相等時，表示隊列為空
    while(front<rear) {
        //隊頭結(jié)點(diǎn)出隊
        p=DeQueue(a);
        displayNode(p);
        //將隊頭結(jié)點(diǎn)的左右孩子依次入隊
        if (p->lchild!=NULL) {
            EnQueue(a, p->lchild);
        }
        if (p->rchild!=NULL) {
            EnQueue(a, p->rchild);
        }
    }
    return 0;
}

??總結(jié)：其實(shí)不管是哪種遍歷方式，我們最終的目的就是訪問所有的樹（子樹）的根節(jié)點(diǎn)，左孩子，右孩子。那么在訪問的過程中，肯定不能一次訪問并打印完畢。這個時候就需要棧來暫存我們已經(jīng)訪問過的元素。在需要的時候?qū)⑵浯蛴〕鰜砑纯桑ㄎ覀円宰蠛⒆庸?jié)點(diǎn)為基準(zhǔn)，先序遍歷是在訪問左孩子節(jié)點(diǎn)之前打印節(jié)點(diǎn)，中序遍歷是在左孩子節(jié)點(diǎn)壓棧之后打印節(jié)點(diǎn)，后序遍歷是在訪問完左右孩子節(jié)點(diǎn)之后打印節(jié)點(diǎn)）。

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：頭號碼甲 > 《待分類》

舉報/認(rèn)領(lǐng)