C語言與Java中二叉樹的非遞歸遍歷方式介紹

本篇內(nèi)容介紹了“C語言與Java中二叉樹的非遞歸遍歷方式介紹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

前言

二叉樹的遞歸遍歷方式很簡單，三種遞歸遍歷方式的區(qū)別，只是printf放的位置不一樣而已，這里就不多講了。把前序遍歷代碼貼在這里：

//結(jié)點
struct Node
{
	int val;
	struct Node* left, * right;
};

//前序遍歷
void pre(Node* root) 
{
    if (root == null)
        return;
    printf("%d ",root->val);
    pre(root->left);
    pre(root->right);
}

前序、中序和后序這三種非遞歸的遍歷方式，中序是最為簡單的，其次是前序，再者就是后序，只是個人感覺?？赡苊總€人感覺都不一樣吧。

一、非遞歸中序遍歷

中序遍歷順序： 左子樹->頭結(jié)點->右子樹。

如圖—出自于《大話數(shù)據(jù)結(jié)構(gòu)》

所以我們首先需要考慮的是將左手邊（左子樹）的結(jié)點壓入棧，當?shù)竭_底部時（NULL），我們就輸出此時棧頂?shù)脑亍?/p>

然后轉(zhuǎn)而去添加當前結(jié)點的右手邊（右子樹）的結(jié)點到棧里。

#define MAXSIZE 20  //整棵樹最大的結(jié)點數(shù)，用于開辟數(shù)組當棧使用
typedef struct Node Node;
void in(Node* root)
{
    Node* stack[MAXSIZE] = { 0 };
    int size = 0; //用于指向arr數(shù)組，也是用于表示這個數(shù)組還有幾個元素
    while (size != 0 || root != NULL)
    {
        if (root != NULL)
        {
            stack[size++] = root;
            root = root->left;  //繼續(xù)往左子樹走
        }
        else
        {
            //此時root為NULL，說明來到了左子樹的最底部，此時輸出棧頂元素，root往右子樹走即可
            printf("%c ", stack[--size]->val);
            root = stack[size]->right;
        }
    }
}

二、非遞歸前序遍歷

前序遍歷順序： 頭結(jié)點->左子樹-> 右子樹

我記得我在B站學算法的時候，聽左程云老師所說，一些的遞歸行為，都可以自己用棧來實現(xiàn)。

確實，三種非遞歸的遍歷方式實則也是需要自己實現(xiàn)棧的功能。接下來的前序遍歷方式，要用到寬度優(yōu)先遍歷的思想，如圖：

圖片出自《大話數(shù)據(jù)結(jié)構(gòu)》

先加入第一層的全部數(shù)據(jù)，然后在棧中使用第一層數(shù)據(jù)的同時，判斷加入第二層的全部數(shù)據(jù)，第三層的也是一樣…

#define MAXSIZE 20  //整棵樹最大的結(jié)點數(shù)，用于開辟數(shù)組當棧使用
typedef struct Node Node;
void pre(Node* root)
{
    if (root == NULL)
        return;

    Node* stack[MAXSIZE] = { 0 }; //模擬棧
    int size = 0; //代表此時棧有多少元素
    arr[size++] = root;
    while (size != 0)
    {
        Node* node = stack[--size];
        printf("%c ", node->val);
        //先壓入右孩子，再壓入左孩子。這樣在彈出的時候才是  先彈出左孩子 然后才是右孩子
        //頭   左   右
        if (node->right != NULL)
            stack[size++] = node->right;
        if (node->left != NULL)
            stack[size++] = node->left;
    }
}

三、非遞歸后序遍歷

在講解了非遞歸的前序遍歷，其實我們在前序遍歷的基礎之上改一下就能完成后序遍歷。我們在將前序遍歷時，在while循環(huán)里，加入左右孩子結(jié)點時，先加入棧的是右孩子，然后才是左孩子，只有這樣，我們彈出來的順序才是先左后右。

現(xiàn)在我們只需要改一下加入左右孩子的順序時，我們先壓入棧是左孩子，然后再壓入右孩子。 這樣彈出來就是先右再左的順序。那此時再加上頭結(jié)點，那就是 頭結(jié)點->右孩子->左孩子 。 此時我們從后面往前面讀，就是 左孩子 -> 右孩子 ->頭結(jié)點。這樣就變成了后序遍歷了。。。

圖片出自《大話數(shù)據(jù)結(jié)構(gòu)》

#define MAXSIZE 20  //整棵樹最大的結(jié)點數(shù)，用于開辟數(shù)組當棧使用
typedef struct Node Node;
void postorder(Node* root)
{
    if (root == NULL)
        return;

    Node* stack1[MAXSIZE] = { 0 }; //主要棧
    Node* stack2[MAXSIZE] = { 0 };  //輔助棧
    int size1 = 0; //主要棧：代表數(shù)組的元素個數(shù)
    int size2 = 0; //輔助棧: 代表數(shù)組的元素個數(shù)
    stack1[size1++] = root;
    while (size1 != 0)
    {
        Node* node = stack1[--size1];
        stack2[size2++] = node; //暫時存入輔助棧

        //先壓入左孩子，再壓入右孩子
        if (node->left != NULL)
            stack1[size1++] = node->left;
        if (node->right != NULL)
            stack1[size1++] = node->right;
    }

    //倒著輸出輔助棧的數(shù)據(jù)即可
    while (size2-- != 0)
        printf("%c ", stack2[size2]->val);
}

“C語言與Java中二叉樹的非遞歸遍歷方式介紹”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！