通俗易懂講解C語言與Java中二叉樹的三種非遞歸遍歷方式

更新時間：2021年09月15日 16:01:25 作者：飛人01_01

二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多的數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變過來的。二叉樹的前，中，后3種遍歷方式，因?yàn)闃涞亩x本身就是遞歸定義的，所以采用遞歸的方法來實(shí)現(xiàn)是很簡單的

詳解二叉樹的三種非遞歸遍歷方式（附C、java源碼）

前言

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

//結(jié)點(diǎn)
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é)點(diǎn)->右子樹。

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

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

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

#define MAXSIZE 20  //整棵樹最大的結(jié)點(diǎn)數(shù)，用于開辟數(shù)組當(dāng)棧使用
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é)點(diǎn)->左子樹-> 右子樹

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

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

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

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

#define MAXSIZE 20  //整棵樹最大的結(jié)點(diǎn)數(shù)，用于開辟數(shù)組當(dāng)棧使用
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;
    }
}

三、非遞歸后序遍歷

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

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

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

#define MAXSIZE 20  //整棵樹最大的結(jié)點(diǎn)數(shù)，用于開辟數(shù)組當(dāng)棧使用
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);
}

非遞歸與遞歸方式的遍歷，有些相似之處，總結(jié)兩種不同的方法，就能更深刻的理解這些方法。最后，C/C++的同學(xué)，記得回收malloc開辟的空間哦?。?！

C語言源碼

java語言源碼

下期見啦?。?！

到此這篇關(guān)于通俗易懂講解C語言中二叉樹的三種非遞歸遍歷方式的文章就介紹到這了,更多相關(guān)C 二叉樹非遞歸遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: