C語(yǔ)言中二叉樹(shù)的后序遍歷詳解

更新時(shí)間：2022年01月24日 16:04:23 作者：guo5411

大家好，本篇文章主要講的是C語(yǔ)言中二叉樹(shù)的后序遍歷詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下

一.二叉樹(shù)的后序遍歷.(遞歸)

思想:

首先我們從二叉樹(shù)的根節(jié)點(diǎn)開(kāi)始先遍歷其左孩子,①接著同樣繼續(xù)遍歷其左孩子的左孩子,直到某個(gè)左孩子節(jié)點(diǎn)的左孩子為NULL時(shí),②開(kāi)始遍歷其右孩子,如果其為NULL則訪問(wèn)該節(jié)點(diǎn)的值域,并返回其雙親節(jié)點(diǎn)重復(fù)第二步的操作,如果其不為NULL則以該節(jié)點(diǎn)為根節(jié)點(diǎn)重復(fù)第一步的操作.直到訪問(wèn)完所有節(jié)點(diǎn)時(shí)結(jié)束遞歸.

代碼:

void BTreePostOrder(struct TreeNode* root,int* arry,int* Size){//后序遍歷
    if(NULL==root){//遞歸出口
        return;
    }
    BTreePostOrder(root->left,arry,Size);//遍歷左孩子
    BTreePostOrder(root->right,arry,Size);//遍歷右孩子
    arry[(*Size)++]=root->val;//訪問(wèn)該節(jié)點(diǎn)
}

運(yùn)行過(guò)程:(如圖)

二.二叉樹(shù)的后序遍歷(迭代)

我們應(yīng)該知道二叉樹(shù)的前中后序遍歷使用遞歸非常的簡(jiǎn)單,但是如果用迭代的話就比較有難度了,因此我思考了很久有沒(méi)有一種迭代類型的算法與遞歸的框架相似(遞歸的三種算法框架非常相似只要會(huì)一個(gè)其他的便很好寫(xiě)出來(lái)),我們是否可以寫(xiě)出一種迭代算法:只用改變?cè)L問(wèn)結(jié)點(diǎn)的次序便可以在迭代的方式下實(shí)現(xiàn)二叉樹(shù)的前中后序遍歷,因此我們使用數(shù)據(jù)結(jié)構(gòu)中棧來(lái)模仿遞歸的形式實(shí)現(xiàn)了二叉樹(shù)的前序遍歷(在進(jìn)棧時(shí)訪問(wèn)結(jié)點(diǎn)值域),中序遍歷(在出棧時(shí)訪問(wèn)結(jié)點(diǎn)的值域),這種方法可以在同一種框架中實(shí)現(xiàn)迭代層面二叉樹(shù)的前序遍歷和中序遍歷,但是到了后序遍歷就沒(méi)辦法了,之后經(jīng)過(guò)思考前序遍歷與后序遍歷的關(guān)系從而實(shí)現(xiàn)了同一種框架中實(shí)現(xiàn)前中后序遍歷的迭代算法.

1.相信很多人在剛學(xué)習(xí)二叉樹(shù)時(shí)都遇到過(guò)這種問(wèn)題,選擇題給定一顆二叉樹(shù),讓我們給出二叉樹(shù)的前中后序遍歷的節(jié)點(diǎn)順序.(每個(gè)人都有自己的計(jì)算方法),下面說(shuō)一下我的計(jì)算方法.

前序:我們按圖中紅色箭頭的順序和其指向依次讀取箭頭上的結(jié)點(diǎn)便可得到其前序遍歷.

中序:我們按圖中紅色箭頭的順序和其指向依次讀取箭頭上的結(jié)點(diǎn)便可得到其中序遍歷.

后序:我們按圖中紅色箭頭的順序和其指向依次讀取箭頭上的結(jié)點(diǎn)便可得到其后序遍歷.

經(jīng)過(guò)上圖我們可以看出二叉樹(shù)的后序遍歷剛好與從右孩子開(kāi)始的前序遍歷所得到的的值完全相反.因此我們可以使用前序遍歷的代碼從右孩子開(kāi)始進(jìn)行前序遍歷,最后將得到的值反向打印即可.

代碼:

typedef struct TreeNode BTNode;
 
typedef struct Stack{//棧的結(jié)構(gòu)體
    BTNode* array[100];
    int size;
}Stack;
 
void StackPush(Stack* a,BTNode* root){//入棧
    a->array[(a->size)++]=root;
}
 
void StackPop(Stack* a){//出棧
    (a->size)--;
}
 
void Reverse(int* a,int Long){//反向打印
    int left_1=0;
    int right_1=Long-1;
    while(left_1 < right_1){
        int temp=a[left_1];
        a[left_1]=a[right_1];
        a[right_1]=temp;
        left_1++;
        right_1--;
    }
}
 
int* postorderTraversal(struct TreeNode* root, int* returnSize){//從右孩子開(kāi)始的前序遍歷
    int* b=(int*)malloc(sizeof(int)*100);
    if(NULL==b){
        printf("申請(qǐng)節(jié)點(diǎn)失敗!\n");
        return NULL;
    }
    Stack a;
    a.size=0;
    BTNode* root_temp;
    int i=0;
    StackPush(&a,root);
    while(NULL != a.array[a.size-1]){
        b[i++]=a.array[a.size-1]->val;
        StackPush(&a,a.array[a.size-1]->right);
        while(NULL == a.array[a.size-1]){
            StackPop(&a);
            if(0 == a.size){
                Reverse(b,i);           
                (*returnSize)=i;
                return b;
            }
            root_temp=a.array[a.size-1];
            StackPop(&a); 
            StackPush(&a,root_temp->left);
        }
    }
    Reverse(b,i);
    (*returnSize)=i;
    return b;
}

從右孩子開(kāi)始的前序遍歷:正常的前序遍歷是先訪問(wèn)節(jié)點(diǎn),然后遍歷其左孩子,再遍歷其右孩子.而該前序遍歷是先訪問(wèn)節(jié)點(diǎn),然后遍歷其右孩子,再遍歷其左孩子.

代碼:

void BTreeInOrder(struct TreeNode* root,int* arry,int* Size){//前序遍歷
    if(NULL==root){//遞歸出口
        return;
    }
    arry[(*Size)++]=root->val;//訪問(wèn)該節(jié)點(diǎn)
    BTreeInOrder(root->right,arry,Size);//遍歷右孩子
    BTreeInOrder(root->left,arry,Size);//遍歷左孩子
}

具體比較如圖: