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

創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括博羅網(wǎng)站建設(shè)、博羅網(wǎng)站制作、博羅網(wǎng)頁制作以及博羅網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，博羅網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到博羅省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

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

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

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

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

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

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

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

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

  分析算法：用樹來描述其執(zhí)行過程；

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

專業(yè)術(shù)語

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

葉子(leaf)（終端結(jié)點(diǎn)），分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)），內(nèi)部結(jié)點(diǎn)（B、C、D、E、H），樹的度（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 層。

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

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

4、有序樹和無序樹

有序樹： 無序樹：

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

對(duì)比樹型結(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ū)，唯一后繼）

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

二叉樹

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

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

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

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

二叉樹的性質(zhì)

性質(zhì)1： 在二叉樹的第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è)可知，由于二叉樹每個(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 的二叉樹至多有 2^k-1個(gè)結(jié)點(diǎn)(k≥1)。

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

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

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

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

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

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

兩類特殊的二叉樹：滿二叉樹和完全二叉樹

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

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

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

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

    2^(k-1)－1<n<=2^k-1 或 2^(k-1)<=n<2^k

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

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

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

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

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

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

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

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

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

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

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

 　

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

總結(jié)：

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

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

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

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

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

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

二叉樹鏈表表示的示例：

遍歷二叉樹和線索二叉樹

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

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

先序遍歷

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

若二叉樹非空

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

   （2）先序遍歷左子樹；

   （3）先序遍歷右子樹；

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

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

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

   （2）先序遍歷左子樹；

   （3）先序遍歷右子樹；

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

對(duì)于先序遍歷來說，藍(lán)色剪頭第一次經(jīng)過的結(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) {        //訪問根節(jié)點(diǎn)
        cout << "先序遍歷" << root->data;
        preorder(root->lchild);
        preorder(root->rchild);
    }// end of if}

非遞歸的先序遍歷

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

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

    1)訪問結(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í)訪問的語句的位置void preorder(BiTree root){    //初始化棧
    stack<BiTree> 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)到右子樹
            p = p->rchild;
        }
    }
}

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

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

若二叉樹非空

 （1）中序遍歷左子樹；

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

 （3）中序遍歷右子樹；

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

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

   （1）中序遍歷左子樹；

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

   （3）中序遍歷右子樹；

中序遞歸遍歷算法

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

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

//非遞歸的中序遍歷二叉樹void inOrder(BiTree root){    //非遞歸中序遍歷（左跟右）
    stack<BiTree> nodes;//初始化棧    //指示指針
    BiNode *p = root;    //遍歷二叉樹的循環(huán)語句
    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();            //訪問根節(jié)點(diǎn)（棧頂結(jié)點(diǎn)）
            cout << p->data << " ";            //使用完畢，彈出            nodes.pop();            //向右遍歷
            p = p->rchild;
        }
    }// end of while}

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

后序遍歷序列:BDFGECA

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

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

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

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

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

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

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

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

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

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站欄目：python二叉樹的存儲(chǔ)方式以及遞歸和非遞歸的三種遍歷方式分別是什么-創(chuàng)新互聯(lián)
文章來源：http://jinyejixie.com/article42/ceshec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、網(wǎng)站設(shè)計(jì)、網(wǎng)頁設(shè)計(jì)公司、ChatGPT、網(wǎng)站改版、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)