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

Posted on by

首先我們從兩個方面講解二叉樹的後序遍歷(遞歸+迭代)

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

思想:

首先我們從二叉樹的根節點開始先遍歷其左孩子,①接著同樣繼續遍歷其左孩子的左孩子,直到某個左孩子節點的左孩子為NULL時,②開始遍歷其右孩子,如果其為NULL則訪問該節點的值域,並返回其雙親節點重復第二步的操作,如果其不為NULL則以該節點為根節點重復第一步的操作.直到訪問完所有節點時結束遞歸.

代碼:

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;//訪問該節點
}

運行過程:(如圖)

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

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

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

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

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

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

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

代碼:

typedef struct TreeNode BTNode;
 
typedef struct Stack{//棧的結構體
    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("申請節點失敗!\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;
}

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

代碼:

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

具體比較如圖:

總結

到此這篇關於C語言中二叉樹的後序遍歷詳解的文章就介紹到這瞭,更多相關C語言二叉樹的後序遍歷內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：