python二叉樹(shù)的存儲(chǔ)方式以及遞歸和非遞歸的三種遍歷方式分別是什么，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

創(chuàng)新互聯(lián)專(zhuān)注于汶上網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供汶上營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，汶上網(wǎng)站制作、汶上網(wǎng)頁(yè)設(shè)計(jì)、汶上網(wǎng)站官網(wǎng)定制、重慶小程序開(kāi)發(fā)服務(wù)，打造汶上網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供汶上網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。

樹(shù)的定義和基本術(shù)語(yǔ)

樹(shù)(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱(chēng)為空樹(shù)，否則它滿足如下兩個(gè)條件：

  (1)有且僅有一個(gè)特定的稱(chēng)為根(Root)的結(jié)點(diǎn)；

  (2)其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集又是一棵樹(shù)，并稱(chēng)其為子樹(shù)(Subtree)。

樹(shù)形結(jié)構(gòu)應(yīng)用實(shí)例：

1、日常生活：家族譜、行政組織結(jié)構(gòu)；書(shū)的目錄

2、計(jì)算機(jī)：資源管理器的文件夾；

    編譯程序：用樹(shù)表示源程序的語(yǔ)法結(jié)構(gòu)；

    數(shù)據(jù)庫(kù)系統(tǒng)：用樹(shù)組織信息；

    分析算法：用樹(shù)來(lái)描述其執(zhí)行過(guò)程；

3、表達(dá)式表示 ( 如 a * b + (c – d / e) * f )

專(zhuān)業(yè)術(shù)語(yǔ)

1、結(jié)點(diǎn)的度(degree)：某結(jié)點(diǎn)的子樹(shù)的分支個(gè)數(shù)

葉子(leaf)（終端結(jié)點(diǎn)），分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)），內(nèi)部結(jié)點(diǎn)（B、C、D、E、H），樹(shù)的度（3）

2、結(jié)點(diǎn)的孩子(child)

雙親(parent)（D為H、I、J的雙親）

兄弟(sibling)(H、I、J互為兄弟)

祖先，子孫(B的子孫為E、K、L、F)

3、結(jié)點(diǎn)的層次

根結(jié)點(diǎn)為第一層。某結(jié)點(diǎn)在第 i 層，其孩子在第 i+1 層。

樹(shù)的深度(depth)就是從跟開(kāi)始往下數(shù)

堂兄弟：雙親在同一層的結(jié)點(diǎn)，互為堂兄弟

4、有序樹(shù)和無(wú)序樹(shù)

有序樹(shù)：  無(wú)序樹(shù)：

5、森林(forest)是 m (m≥0) 棵互不相交的樹(shù)的集合。

對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)

線性結(jié)構(gòu)：第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其它數(shù)據(jù)元素一個(gè)前驅(qū)、一個(gè)后繼。（唯一頭結(jié)點(diǎn)，唯一尾節(jié)點(diǎn)；中間結(jié)點(diǎn)有唯一前驅(qū)，唯一后繼）

樹(shù)形結(jié)構(gòu)：根節(jié)點(diǎn)無(wú)前驅(qū)，多個(gè)葉子節(jié)點(diǎn)無(wú)后繼，其它元素一個(gè)前驅(qū)，多個(gè)后繼。（唯一根結(jié)點(diǎn)；多個(gè)葉結(jié)點(diǎn)；中間結(jié)點(diǎn)有唯一前驅(qū)，多個(gè)后繼）

二叉樹(shù)

把滿足以下兩個(gè)條件的樹(shù)型結(jié)構(gòu)叫做二叉樹(shù)（Binary Tree）：

   （1）每個(gè)結(jié)點(diǎn)的度都不大于2；

   （2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。即使只有一棵子樹(shù)也要進(jìn)行區(qū)分，說(shuō)明它是左子樹(shù)，還是右子樹(shù)。這是二叉樹(shù)與樹(shù)的最主要的差別。

二叉樹(shù)一共有5種形態(tài)

二叉樹(shù)的性質(zhì)

性質(zhì)1： 在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>=1)。

采用歸納法證明此性質(zhì)。

  （1）當(dāng)i=1時(shí)，2^( i-1)=2^0 =1,命題成立。

  （2）假定i=k時(shí)命題成立，即第k層最多有2^(k-1)個(gè)結(jié)點(diǎn)；

  （3）由歸納假設(shè)可知，由于二叉樹(shù)每個(gè)結(jié)點(diǎn)的度最大為2，故在第k+1層上最大結(jié)點(diǎn)數(shù)為第k層上最大結(jié)點(diǎn)數(shù)的2倍，

           即2×2^(k-1)＝2^k=2^(k+1)-1

命題得到證明。

性質(zhì)2 ：深度為 k 的二叉樹(shù)至多有 2^k-1個(gè)結(jié)點(diǎn)(k≥1)。

證明：由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為  

性質(zhì)3： 對(duì)任何一棵二叉樹(shù)，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。

證明：設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2   （1）

         又二叉樹(shù)上分支總數(shù) b = n1+2n2           （2）

而除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有分支進(jìn)入，即 b = n-1

將（1）（2）式代入，得 n0 = n2 + 1 。

兩類(lèi)特殊的二叉樹(shù)：滿二叉樹(shù)和完全二叉樹(shù)

滿二叉樹(shù)：一棵深度為k且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。

完全二叉樹(shù)：樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。（編號(hào)的規(guī)則為，由上到下，從左到右。）

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2 n]＋1。

證明：假設(shè)此二叉樹(shù)的深度為k，則根據(jù)性質(zhì)2及完全二叉樹(shù)的定義得到：

     2^(k-1)－1

取對(duì)數(shù)得到：k－1 <= log2 n < k  因?yàn)閗是整數(shù)。所以有：k＝【log2n】＋1。

性質(zhì)5： 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)（從第1層到第【log2n】+1層，每層從左到右),則對(duì)任一結(jié)點(diǎn)i（1<=i<=n),有：

1）如果i＝1，則結(jié)點(diǎn)i無(wú)雙親，是二叉樹(shù)的根；如果i>1，則其雙親是結(jié)點(diǎn)【i/2】。

2）如果2i>n，則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子是結(jié)點(diǎn)2i。

3）如果2i＋1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i＋1。

所示為完全二叉樹(shù)上結(jié)點(diǎn)及其左右孩子結(jié)點(diǎn)之間的關(guān)系。

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

1）順序存儲(chǔ)結(jié)構(gòu)

完全二叉樹(shù)：用一組連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)各結(jié)點(diǎn)元素。即將完全二叉樹(shù)上編號(hào)為i  的結(jié)點(diǎn)的值存儲(chǔ)在下標(biāo)為 i-1 的數(shù)組元素中。結(jié)點(diǎn)間的關(guān)系可由公式計(jì)算得到。

一般情形的二叉樹(shù)：增添一些空結(jié)點(diǎn)使變成完全二叉樹(shù)形態(tài)，再按上述方法存儲(chǔ)。

如圖完全二叉樹(shù)的存儲(chǔ)

單只二叉樹(shù)的存儲(chǔ)

總結(jié)：

1、完全二叉樹(shù)用順序存儲(chǔ)既節(jié)約空間，存取也方便；

2、一般二叉樹(shù)用順序存儲(chǔ)，空間較浪費(fèi)，最壞情況為右單支二叉樹(shù)。（一個(gè)深度為K且只有K個(gè)節(jié)點(diǎn)的單支樹(shù)卻需要長(zhǎng)度為2^k-1的一維數(shù)組）

2）二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)方式

常用的有二叉鏈表和三叉鏈表存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)的左右孩子或雙親靠指針來(lái)指示

有時(shí)也可用數(shù)組的下標(biāo)來(lái)模擬指針,即開(kāi)辟三個(gè)一維數(shù)組Data ,lchild,rchild 分別存儲(chǔ)結(jié)點(diǎn)的元素及其左,右指針域;下面是鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)表示：

typedef struct BiNode{    int data;//數(shù)據(jù)域
    BiNode *lchild, *rchild;//左右孩子指針} BiNode, *BiTree;

二叉樹(shù)鏈表表示的示例：

遍歷二叉樹(shù)和線索二叉樹(shù)

任何一個(gè)非空的二叉樹(shù)都由三部分構(gòu)成

樹(shù)的遍歷是訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)僅一次的過(guò)程。遍歷可以被認(rèn)為是把所有的結(jié)點(diǎn)放在一條線上，新航道雅思培訓(xùn)或者將一棵樹(shù)進(jìn)行線性化的處理。

先序遍歷

DLR根左右：訪問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)、先序遍歷右子樹(shù)

若二叉樹(shù)非空

    （1）訪問(wèn)根結(jié)點(diǎn)；

    （2）先序遍歷左子樹(shù)；

    （3）先序遍歷右子樹(shù)；

若二叉樹(shù)為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）

若二叉樹(shù)非空——遞歸項(xiàng)

    （1）訪問(wèn)根結(jié)點(diǎn)；

    （2）先序遍歷左子樹(shù)；

    （3）先序遍歷右子樹(shù)；

主要過(guò)程就是遞歸調(diào)用，也可以用棧來(lái)實(shí)現(xiàn)。

對(duì)于先序遍歷來(lái)說(shuō)，藍(lán)色剪頭第一次經(jīng)過(guò)的結(jié)點(diǎn)，就是遍歷的序列，以后再次經(jīng)歷就不算進(jìn)去了。

typedef struct BiNode{    int data;//數(shù)據(jù)域
    BiNode *lchild, *rchild;//左右孩子指針} BiNode, *BiTree;void preorder(BiNode *root){    if (root != NULL) {        //訪問(wèn)根節(jié)點(diǎn)
        cout << "先序遍歷" << root->data;
        preorder(root->lchild);
        preorder(root->rchild);
    }// end of if}

非遞歸的先序遍歷

根據(jù)前序遍歷訪問(wèn)的順序，優(yōu)先訪問(wèn)根結(jié)點(diǎn)，然后再分別訪問(wèn)左孩子和右孩子。即對(duì)于任一結(jié)點(diǎn)，其可看做是根結(jié)點(diǎn)，因此可以直接訪問(wèn)，訪問(wèn)完之后，若其左孩子不為空，按相同規(guī)則訪問(wèn)它的左子樹(shù)；當(dāng)訪問(wèn)其左子樹(shù)時(shí)，再訪問(wèn)它的右子樹(shù)。因此其處理過(guò)程如下：

對(duì)于任一結(jié)點(diǎn)P：

     1)訪問(wèn)結(jié)點(diǎn)P，并將結(jié)點(diǎn)P入棧;

     2)判斷結(jié)點(diǎn)P的左孩子是否為空，若為空，則取棧頂結(jié)點(diǎn)并進(jìn)行出棧操作，并將棧頂結(jié)點(diǎn)的右孩子置為當(dāng)前的結(jié)點(diǎn)P，循環(huán)至1);若不為空，則將P的左孩子置為當(dāng)前的結(jié)點(diǎn)P;

     3)直到P為NULL并且棧為空，則遍歷結(jié)束。

//關(guān)鍵在于何時(shí)訪問(wèn)的語(yǔ)句的位置void preorder(BiTree root){    //初始化棧
    stack nodes;
    BiNode *p = root;    while (p != NULL || !nodes.empty()) {        while (p != NULL) {            //根左右的順序遍歷
            cout << p->data;            //進(jìn)棧            nodes.push(p);            //繼續(xù)移動(dòng)
            p = p->lchild;
        }        //p == null
        if (!nodes.empty()) {            //對(duì) p 重新指向
            p = nodes.top();            //出棧            nodes.pop();            //轉(zhuǎn)到右子樹(shù)
            p = p->rchild;
        }
    }
}

中序遍歷、后序遍歷和先序遍歷思想基本類(lèi)似，對(duì)于中序遍歷來(lái)說(shuō)，藍(lán)色剪頭第二次經(jīng)過(guò)的結(jié)點(diǎn)，就是遍歷的序列，之前的和以后的再次經(jīng)歷就不算進(jìn)序列里去了。對(duì)于后序遍歷來(lái)說(shuō)，藍(lán)色剪頭第三次經(jīng)過(guò)的結(jié)點(diǎn)，就是遍歷的序列，之前經(jīng)歷的就不算進(jìn)去了。

LDR左跟右：中序遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、中序遍歷右子樹(shù)

若二叉樹(shù)非空

  （1）中序遍歷左子樹(shù)；

  （2）訪問(wèn)根結(jié)點(diǎn)；

  （3）中序遍歷右子樹(shù)；

若二叉樹(shù)為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)）

若二叉樹(shù)非空——遞歸項(xiàng)

    （1）中序遍歷左子樹(shù)；

    （2）訪問(wèn)根結(jié)點(diǎn)；

    （3）中序遍歷右子樹(shù)；

中序遞歸遍歷算法

void inOrder(BiNode *root){    if (root != NULL) {
        inOrder(root->lchild);
        cout << "先序遍歷" << root->data;
        inOrder(root->rchild);
    }// end of if}

中序的非遞歸遍歷，使用棧

//非遞歸的中序遍歷二叉樹(shù)void inOrder(BiTree root){    //非遞歸中序遍歷（左跟右）
    stack nodes;//初始化棧    //指示指針
    BiNode *p = root;    //遍歷二叉樹(shù)的循環(huán)語(yǔ)句
    while (p != NULL || !nodes.empty()) {        while (p != NULL) {            //不為空就入棧            nodes.push(p);            //一直向做走，直到為 kong
            p = p->lchild;
        }        // 需要判斷空否，因?yàn)樾枰鰲２僮?
        if (!nodes.empty()) {            //令 p 重新指向 棧頂結(jié)點(diǎn)
            p = nodes.top();            //訪問(wèn)根節(jié)點(diǎn)（棧頂結(jié)點(diǎn)）
            cout << p->data << " ";            //使用完畢，彈出            nodes.pop();            //向右遍歷
            p = p->rchild;
        }
    }// end of while}

LRD左右跟：后序遍歷左子樹(shù)、后序遍歷右子樹(shù)、訪問(wèn)根結(jié)點(diǎn)

后序遍歷序列:BDFGECA

//遞歸后續(xù)遍歷二叉樹(shù)void lastOrder(BiTree root){    if (root != NULL) {
        lastOrder(root->lchild);
        lastOrder(root->rchild);
        cout << root->data;
    }
}

同理有非遞歸的后續(xù)遍歷二叉樹(shù)

在后序遍歷中，要保證左孩子和右孩子都已被訪問(wèn)，并且左孩子在右孩子訪問(wèn)之后才能訪問(wèn)根結(jié)點(diǎn)。因此對(duì)于任一結(jié)點(diǎn)P，先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問(wèn)它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問(wèn)過(guò)了，則同樣可以直接訪問(wèn)該結(jié)點(diǎn)。若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(shí)候，左孩子在右孩子前面被訪問(wèn)，左孩子和右孩子都在根結(jié)點(diǎn)前面被訪問(wèn)。

void postOrder3(BiTree root)     //非遞歸后序遍歷{
    stack nodes;    //當(dāng)前結(jié)點(diǎn)
    BiNode *cur;    //前一次訪問(wèn)的結(jié)點(diǎn)
    BiNode *pre = NULL;    //根節(jié)點(diǎn)入棧    nodes.push(root);    //依次遍歷左右子樹(shù)
    while(!nodes.empty())
    {
        cur = nodes.top();        //判斷 cur 結(jié)點(diǎn)的左右孩子子樹(shù)的情況
        if((cur->lchild == NULL && cur->rchild == NULL) ||
           (pre != NULL && (pre == cur->lchild || pre == cur->rchild)))
        {            //如果當(dāng)前結(jié)點(diǎn)沒(méi)有孩子結(jié)點(diǎn)或者孩子節(jié)點(diǎn)都已被訪問(wèn)過(guò)
            cout << cur->data;            //出棧            nodes.pop();            //前一次訪問(wèn)的結(jié)點(diǎn)， pre標(biāo)記已經(jīng)訪問(wèn)的結(jié)點(diǎn)
            pre = cur;
        }        else
        {            //左右跟的訪問(wèn)順序，關(guān)鍵還是訪問(wèn)語(yǔ)句的位置?。?！一定是先寫(xiě)右子樹(shù)，再寫(xiě)左子樹(shù)，順序不能錯(cuò)            //如果當(dāng)前結(jié)點(diǎn)的右子樹(shù)不為空
            if(cur->rchild != NULL){
                nodes.push(cur->rchild);
            }            //如果當(dāng)前結(jié)點(diǎn)的左子樹(shù)不為空
            if(cur->lchild != NULL){
                nodes.push(cur->lchild);
            }
        }
    }
}

二叉樹(shù)遍歷的總結(jié)：

無(wú)論先序、中序、后序遍歷二叉樹(shù)，遍歷時(shí)的搜索路線是相同的：從根節(jié)點(diǎn)出發(fā)，逆時(shí)針延二叉樹(shù)外緣移動(dòng)，對(duì)每個(gè)節(jié)點(diǎn)均途經(jīng)三次。

先序遍歷：第一次經(jīng)過(guò)節(jié)點(diǎn)時(shí)訪問(wèn)。（ABCD）

中序遍歷：第二次經(jīng)過(guò)節(jié)點(diǎn)時(shí)訪問(wèn)。（BADC）

后序遍歷：第三次經(jīng)過(guò)節(jié)點(diǎn)時(shí)訪問(wèn)。（BDCA）

看完上述內(nèi)容，你們掌握python二叉樹(shù)的存儲(chǔ)方式以及遞歸和非遞歸的三種遍歷方式分別是什么的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！