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

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

展開全文

先序遍歷規(guī)則

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

先序遍歷舉例

??如圖所示，采用先序遍歷訪問這顆二叉樹的詳細過程為：
??1.訪問該二叉樹的根節(jié)點，找到 1；
??2.訪問節(jié)點 1 的左子樹，找到節(jié)點 2；
??3.訪問節(jié)點 2 的左子樹，找到節(jié)點 4；
??4.由于訪問節(jié)點 4 左子樹失敗，且也沒有右子樹，因此以節(jié)點 4 為根節(jié)點的子樹遍歷完成。但節(jié)點 2 還沒有遍歷其右子樹，因此現在開始遍歷，即訪問節(jié)點 5；
??5.由于節(jié)點 5 無左右子樹，因此節(jié)點 5 遍歷完成，并且由此以節(jié)點 2 為根節(jié)點的子樹也遍歷完成?，F在回到節(jié)點 1 ，并開始遍歷該節(jié)點的右子樹，即訪問節(jié)點 3；
??6.訪問節(jié)點 3 左子樹，找到節(jié)點 6；
??7.由于節(jié)點 6 無左右子樹，因此節(jié)點 6 遍歷完成，回到節(jié)點 3 并遍歷其右子樹，找到節(jié)點 7；
??8.節(jié)點 7 無左右子樹，因此以節(jié)點 3 為根節(jié)點的子樹遍歷完成，同時回歸節(jié)點 1。由于節(jié)點 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
//構造結點的結構體
typedef struct BiTNode{
    TElemType data;//數據域
    struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;

/**
 * @Description: 初始化樹的函數
 * @Param: BiTree *T 結構體指針的指針
 * @Return: 無
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    //根節(jié)點
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    //1節(jié)點的左孩子2
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //2節(jié)點的右孩子5
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    //1節(jié)點的右孩子3
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    //3節(jié)點的左孩子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é)點的右孩子7
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    //2節(jié)點的左孩子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: 先序遍歷
 * @Param: BiTree T 結構體指針
 * @Return: 無
 * @Author: Carlos
 */
void PreOrderTraverse(BiTree T){
    if (T) {
        PrintBiT(T);//調用操作結點數據的函數方法
        PreOrderTraverse(T->lchild);//訪問該結點的左孩子
        PreOrderTraverse(T->rchild);//訪問該結點的右孩子
    }
    //如果結點為空，返回上一層
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍歷: \n");
    PreOrderTraverse(Tree);
}

先序遍歷代碼（非遞歸）

??因為要在遍歷完某個樹的根節(jié)點的左子樹后接著遍歷節(jié)點的右子樹，為了能找到該樹的根節(jié)點，需要使用棧來進行暫存。中序和后序也都涉及到回溯，所以都需要用到棧。

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

中序遍歷

中序遍歷規(guī)則

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

中序遍歷舉例

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

中序遍歷代碼（遞歸）

/*
 * @Description: 遞歸實現的中序遍歷
 * @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
//構造結點的結構體
typedef struct BiTNode{
    //數據域
    TElemType data;
    //左右孩子指針
    struct BiTreelchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化樹
 * @Param: BiTree *T  結構體指針的指針（指針數組）
 * @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: 顯示函數
 * @Param: BiTree elem 結構體指針
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 中序遍歷
 * @Param: BiTree T 結構體指針
 * @Return: 無
 * @Author: Carlos
 */
void INOrderTraverse(BiTree T){
    if (T) {
        INOrderTraverse(T->lchild);//遍歷左孩子
        PrintBiT(T);//調用操作結點數據的函數方法
        INOrderTraverse(T->rchild);//遍歷右孩子
    }
    //如果結點為空，返回上一層
    return;
}

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

中序遍歷代碼（非遞歸）

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

/*
 * @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變量時刻表示棧頂元素所在位置
//構造結點的結構體
typedef struct BiTNode{
    //數據域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化樹
 * @Param: BiTree *T  結構體指針的指針
 * @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: 中序遍歷使用的進棧函數
 * @Param: BiTree* a 指向樹的指針數組 BiTree elem 進棧的元素
 * @Return: 無
 * @Author: Carlos
 */
void Push(BiTree* a,BiTree elem){
    //指針進棧
    a[++top]=elem;
}
/**
 * @Description: 前序遍歷使用的彈棧函數
 * @Param: 無
 * @Return: 無
 * @Author: Carlos
 */
void Pop( ){
    if (top==-1) {
        return;
    }
    top--;
}
/**
 * @Description: 顯示函數
 * @Param: BiTree elem 指向樹的指針
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 拿到棧頂元素
 * @Param: BiTree*a 指針數組
 * @Return: 棧頂元素的地址
 * @Author: Carlos
 */
BiTree GetTop(BiTree*a){
    return a[top];
}
/**
 * @Description: 中序遍歷非遞歸算法，先左，然后回退，然后右。從根結點開始，遍歷左孩子同時壓棧，當遍歷結束，說明當前遍歷的結點沒有左孩子，
 * 從棧中取出來調用操作函數，然后訪問該結點的右孩子，繼續(xù)以上重復性的操作
 * @Return: 棧頂元素的地址
 * @Author: Carlos
 */
void InOrderTraverse1(BiTree Tree){
    //定義一個順序棧
    BiTree a[20];
    //臨時指針
    BiTree p;
    //根結點進棧
    Push(a, Tree);
    //top!=-1說明棧內不為空，程序繼續(xù)運行
    while (top!=-1) {
        //一直取棧頂元素，且不能為NULL
        while ((p=GetTop(a)) &&p){
            //將該結點的左孩子進棧，如果沒有左孩子，NULL進棧
            Push(a, p->lchild);
        }
        //跳出循環(huán)，棧頂元素肯定為NULL，將NULL彈棧。 打印的第一個元素沒有右孩子，所以也會Pop掉，再取棧頂元素就是第一個元素的父節(jié)點
        Pop();
        if (top!=-1) {
            //取棧頂元素
            p=GetTop(a);
            //棧頂元素彈棧
            Pop();
            //遍歷完所有左孩子之后，打印棧頂的元素。
            PrintBiT(p);
            //將p指向的結點的右孩子進棧
            Push(a, p->rchild);
        }
    }
}
/**
 * @Description: 中序遍歷非遞歸算法。中序遍歷過程中，只需將每個結點的左子樹壓棧即可，右子樹不需要壓棧。
 * 當結點的左子樹遍歷完成后，只需要以棧頂結點的右孩子為根結點，繼續(xù)循環(huán)遍歷即可
 * @Param: 無
 * @Return: 棧頂元素的地址
 * @Author: Carlos
 */
void InOrderTraverse2(BiTree Tree){
    //定義一個順序棧
    BiTree a[20];
    //臨時指針
    BiTree p;
    p=Tree;
    //當p為NULL或者棧為空時，表明樹遍歷完成
    while (p || top!=-1) {
        //如果p不為NULL，將其壓棧并遍歷其左子樹
        if (p) {
            Push(a, p);
            p=p->lchild;
        }
        //如果p==NULL，表明左子樹遍歷完成，需要遍歷上一層結點的右子樹  彈出時順便訪問右子樹
        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ī)則

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

后序遍歷舉例

在這里插入圖片描述
??如上圖中，對此二叉樹進行后序遍歷的操作過程為：
??從根節(jié)點 1 開始，遍歷該節(jié)點的左子樹（以節(jié)點 2 為根節(jié)點）；
??1.遍歷節(jié)點 2 的左子樹（以節(jié)點 4 為根節(jié)點）；
??2.由于節(jié)點 4 既沒有左子樹，也沒有右子樹，此時訪問該節(jié)點中的元素 4，并回退到節(jié)點 2 ，遍歷節(jié)點 2 的右子樹（以 5 為根節(jié)點）；
??3.由于節(jié)點 5 無左右子樹，因此可以訪問節(jié)點 5 ，并且此時節(jié)點 2 的左右子樹也遍歷完成，因此也可以訪問節(jié)點 2；
??4.此時回退到節(jié)點 1 ，開始遍歷節(jié)點 1 的右子樹（以節(jié)點 3 為根節(jié)點）；
??5.遍歷節(jié)點 3 的左子樹（以節(jié)點 6 為根節(jié)點）；
??6.由于節(jié)點 6 無左右子樹，因此訪問節(jié)點 6，并回退到節(jié)點 3，開始遍歷節(jié)點 3 的右子樹（以節(jié)點 7 為根節(jié)點）；
??7.由于節(jié)點 7 無左右子樹，因此訪問節(jié)點 7，并且節(jié)點 3 的左右子樹也遍歷完成，可以訪問節(jié)點 3；節(jié)點 1 的左右子樹也遍歷完成，可以訪問節(jié)點 1；
??由此，對上圖中二叉樹進行后序遍歷的結果為：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
//構造結點的結構體
typedef struct BiTNode{
    //數據域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
* @Description: 初始化樹
* @Param: BiTree *T  結構體指針
* @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: 顯示函數
* @Param: BiTree elem 指向樹的結構體指針
* @Return: 無
* @Author: Carlos
*/
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
* @Description: 先序遍歷
* @Param: BiTree T 指針數組，存放各個節(jié)點的指針
* @Return: 無
* @Author: Carlos
*/
void PreOrderTraverse(BiTree T){
    if (T) {
        PreOrderTraverse(T->lchild);//訪問該結點的左孩子
        PreOrderTraverse(T->rchild);//訪問該結點的右孩子
         PrintBiT(T);//調用操作結點數據的函數方法
    }
    //如果結點為空，返回上一層
    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;
//構造結點的結構體
typedef struct BiTNode{
    //數據域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化樹
 * @Param: BiTree *T  結構體指針數組
 * @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: 無
 * @Return: 無
 * @Author: Carlos
 */
void Pop( ){
    if (top==-1) {
        return ;
    }
    top--;
}
/**
 * @Description: 顯示函數
 * @Param: 無
 * @Return: 無
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}

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

層次遍歷

層次遍歷規(guī)則

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

層次遍歷舉例

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

層次遍歷代碼

/*
 * @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{
    //數據域
    TElemType data;
    //左右孩子指針
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//采用順序隊列，初始化創(chuàng)建隊列數組
BiTree a[20];
/**
 * @Description: 初始化二叉樹
 * @Param: BiTree *T 二叉樹的結構體指針數組
 * @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 二叉樹結構體指針  BiTree node 入隊的節(jié)點
 * @Return: 無
 * @Author: Carlos
 */
void EnQueue(BiTree *a,BiTree node){
    a[rear++]=node;
}
/**
 * @Description: 出隊
 * @Param: BiTree *node 二叉樹結構體指針數組
 * @Return: 結構體指針
 * @Author: Carlos
 */
BiTree DeQueue(BiTree *node){
    return a[front++];
}
/**
 * @Description: 二叉樹輸出函數
 * @Param: BiTree node 輸出的節(jié)點
 * @Return: 無
 * @Author: Carlos
 */
void displayNode(BiTree node){
    printf("%d ",node->data);
}
int main() {
    BiTree tree;
    //初始化二叉樹
    CreateBiTree(&tree);
    BiTree p;

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

??總結：其實不管是哪種遍歷方式，我們最終的目的就是訪問所有的樹（子樹）的根節(jié)點，左孩子，右孩子。那么在訪問的過程中，肯定不能一次訪問并打印完畢。這個時候就需要棧來暫存我們已經訪問過的元素。在需要的時候將其打印出來即可（我們以左孩子節(jié)點為基準，先序遍歷是在訪問左孩子節(jié)點之前打印節(jié)點，中序遍歷是在左孩子節(jié)點壓棧之后打印節(jié)點，后序遍歷是在訪問完左右孩子節(jié)點之后打印節(jié)點）。