python二叉樹的存儲方式以及遞歸和非遞歸的三種遍歷方式分別是什么

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

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

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

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

  (2)其余的結(jié)點(diǎn)可分為m(m>=0)個互不相交的子集T1,T2,T3…Tm，其中每個子集又是一棵樹，并稱其為子樹(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)的子樹的分支個數(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) 棵互不相交的樹的集合。

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

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

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

二叉樹

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

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

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

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

二叉樹的性質(zhì)

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

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

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

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

  （3）由歸納假設(shè)可知，由于二叉樹每個結(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個結(jié)點(diǎn)(k≥1)。

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

性質(zhì)3： 對任何一棵二叉樹，如果其終端結(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個結(jié)點(diǎn)的二叉樹。

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

性質(zhì)4：具有n個結(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

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

性質(zhì)5： 如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號（從第1層到第【log2n】+1層，每層從左到右),則對任一結(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)系。

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

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

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

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

如圖完全二叉樹的存儲

單只二叉樹的存儲

總結(jié)：

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

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

2）二叉樹的鏈?zhǔn)酱鎯Ψ绞?/p>

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

有時也可用數(shù)組的下標(biāo)來模擬指針,即開辟三個一維數(shù)組Data ,lchild,rchild 分別存儲結(jié)點(diǎn)的元素及其左,右指針域;下面是鏈?zhǔn)酱鎯Φ亩鏄浔硎荆?/p>

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

二叉樹鏈表表示的示例：

遍歷二叉樹和線索二叉樹

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

樹的遍歷是訪問樹中每個結(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)。

對于先序遍歷來說，藍(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)，然后再分別訪問左孩子和右孩子。即對于任一結(jié)點(diǎn)，其可看做是根結(jié)點(diǎn)，因此可以直接訪問，訪問完之后，若其左孩子不為空，按相同規(guī)則訪問它的左子樹；當(dāng)訪問其左子樹時，再訪問它的右子樹。因此其處理過程如下：

對于任一結(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)鍵在于何時訪問的語句的位置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ù)移動
            p = p->lchild;
        }        //p == null
        if (!nodes.empty()) {            //對 p 重新指向
            p = nodes.top();            //出棧            nodes.pop();            //轉(zhuǎn)到右子樹
            p = p->rchild;
        }
    }
}

中序遍歷、后序遍歷和先序遍歷思想基本類似，對于中序遍歷來說，藍(lán)色剪頭第二次經(jīng)過的結(jié)點(diǎn)，就是遍歷的序列，之前的和以后的再次經(jīng)歷就不算進(jìn)序列里去了。對于后序遍歷來說，藍(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)。因此對于任一結(jié)點(diǎn)P，先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結(jié)點(diǎn)。若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結(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)鍵還是訪問語句的位置?。。∫欢ㄊ窍葘懹易訕?，再寫左子樹，順序不能錯            //如果當(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é)：

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

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

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

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

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