快捷導(dǎo)航

C語言中二叉樹的后序遍歷詳解

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

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

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

思想:

首先我們從二叉樹的根節(jié)點開始先遍歷其左孩子,①接著同樣繼續(xù)遍歷其左孩子的左孩子,直到某個左孩子節(jié)點的左孩子為NULL時,②開始遍歷其右孩子,如果其為NULL則訪問該節(jié)點的值域,并返回其雙親節(jié)點重復(fù)第二步的操作,如果其不為NULL則以該節(jié)點為根節(jié)點重復(fù)第一步的操作.直到訪問完所有節(jié)點時結(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;//訪問該節(jié)點
}

運行過程:(如圖)

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

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

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

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

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

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

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

代碼:

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){//從右孩子開始的前序遍歷
    int* b=(int*)malloc(sizeof(int)*100);
    if(NULL==b){
        printf("申請節(jié)點失敗!\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;
}

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

代碼:

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

具體比較如圖: