C語言中如何實現二叉樹的后序遍歷

小編給大家分享一下C語言中如何實現二叉樹的后序遍歷，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

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

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

思想:

首先我們從二叉樹的根節點開始先遍歷其左孩子,①接著同樣繼續遍歷其左孩子的左孩子,直到某個左孩子節點的左孩子為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語言中如何實現二叉樹的后序遍歷”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！