亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        二叉樹創(chuàng)建方法

        2021-07-09 17:19:40陳文
        現(xiàn)代計算機 2021年14期
        關鍵詞:程序方法

        陳文

        (福州職業(yè)技術學院,福州 350108)

        0 引言

        二叉樹是《數(shù)據(jù)結構與算法》課程的重要內容,它是典型的樹型數(shù)據(jù)結構[1],二叉樹的結構及二叉樹的算法已廣泛應用各類程序設計中[2-3]。分析研究二叉樹的應用,首先要基于二叉樹已經(jīng)創(chuàng)建的前提下進行。因此,二叉樹的創(chuàng)建則是一切二叉樹算法應用的基礎。然而,《數(shù)據(jù)結構與算法》的教材中,往往注重介紹二叉樹的遍歷方法及二叉樹應用等,對二叉樹的創(chuàng)建并未給出詳細的分析。由于二叉樹的遍歷算法是基于二叉樹已經(jīng)創(chuàng)建的前提下,而本文所介紹的二叉樹創(chuàng)建方法,卻要用到二叉樹的遍歷等遞歸思想,因此,本文所介紹的二叉樹創(chuàng)建方法是學完二叉樹遍歷等相關理論后,反過來進一步總結與分析二叉樹的創(chuàng)建思想。它是對《數(shù)據(jù)結構與算法》教材的必要說明與補充。

        本文著重介紹二叉樹的創(chuàng)建方法,闡述二叉樹創(chuàng)建的遞歸原理及二叉樹創(chuàng)建的程序框架。并結合樣例驗證其正確性。同時,對學習二叉樹的其他算法具有輔助作用。

        1 直接遞歸創(chuàng)建二叉樹

        1.1 二叉樹創(chuàng)建分析

        以圖1 所示的二叉樹為例,二叉樹的創(chuàng)建可用遞歸法創(chuàng)建。方法如圖1。

        圖1 二叉樹樣例圖

        首先,創(chuàng)建根結點root,其值為a,再依次創(chuàng)建左子樹及右子樹。即輸入序列如圖2。

        圖2

        二叉樹的創(chuàng)建遞歸為根結點及左右子樹的創(chuàng)建[4]。

        為了使遞歸程序順利執(zhí)行,必須增加遞歸的出口條件。不妨以“#”字符表示為空結點作為出口條件,則二叉樹可形象表示為圖3。

        圖3 補充空結點后的二叉樹

        輸入序列為圖4。

        圖4

        進一步轉化為圖5。

        圖5

        完整的輸入序列為:abd##eg##h##c#f##。

        1.2 程序框架

        本文利用C 語言程序設計描述結點的結構與程序框架,通過以上的分析可知:

        結點結構:

        二叉樹創(chuàng)建的程序框架為:

        1.3 程序運行結果

        為驗證所創(chuàng)建的二叉樹正確性,可將其前序、中序、后序輸出。二叉樹前序、中序及后序的遍歷方法有眾多資料分析討論[5],常用的遞歸算法如下:

        前序算法:

        中序算法:

        后序算法:

        主程序:

        運行結算如圖6 所示。

        圖6 運行結果圖

        2 利用前序與中序的遍歷結果,構造二叉樹

        2.1 二叉樹與前序遍歷的關系

        二叉樹與前序遍歷結果存在多對一的關系。如二叉樹1。

        圖7 二叉樹1

        與二叉樹2。

        圖8 二叉樹2

        前序遍歷結果均為:abdeghcf。

        由此可見,單從二叉樹的前序遍歷無法構建二叉樹。

        同樣,單從二叉樹的中序遍歷或后序遍歷也無法構建二叉樹。

        2.2 由前序及中序遍歷結果構建二叉樹

        由前序及中序遍歷結果可唯一確定二叉樹。以圖1 的二叉樹為例,分析如下:

        前序遍歷abdeghcf。

        中序遍歷dbgehacf。

        由前序遍歷可知:a 為根結點。

        再由中序遍歷可知:左子樹序列為dbgeh,右子樹為序列為cf。

        于是二叉樹遞歸為圖9。

        圖9 遞歸分析圖

        遞歸的出口條件為前序或中序序列為空時,該二叉樹為空樹。

        2.3 由前序及中序遍歷結果構建二叉樹的程序框架

        形參說明:

        predata[]、indata[]:前序及中序數(shù)組

        pre1、in1:前序序列及中序序列起始位置

        len:序列的長度

        程序分析:

        根結點字符為ch=predate[pre1]

        ch 在中序中的位置loc=lookfor(indata,ch)

        則:左子樹序列長度llen=loc-in1

        右子樹序列長度rlen=len-llen-1

        于是:前序序列predata 各位置元素如圖10。

        圖10

        中序序列indata 各位置元素如圖11。程序框架:

        圖11

        其中,函數(shù)lookfor(char*data,char ch)表示從數(shù)組data[]中查找字符ch,具體實現(xiàn)方法如下:

        程序運行結果如上例中的圖6 所示。

        3 利用后序與中序的遍歷結果,構造二叉樹

        程序的基本思想與“利用前序與中序的遍歷結果,構造二叉樹”相似。不再贅述。

        4 結語

        二叉樹算法中普遍使用遞歸方法,本文提出二叉樹的創(chuàng)建也是基于遞歸思想,因此,二叉樹創(chuàng)建的研究探討,有助于理解遞歸原理。將二叉樹創(chuàng)建與二叉樹其他算法相結合,有助于加深對二叉樹的理解。同時,對提高二叉樹的應用能力無疑具有積極意義。

        猜你喜歡
        程序方法
        學習方法
        試論我國未決羈押程序的立法完善
        人大建設(2019年12期)2019-05-21 02:55:44
        失能的信仰——走向衰亡的民事訴訟程序
        “程序猿”的生活什么樣
        英國與歐盟正式啟動“離婚”程序程序
        可能是方法不對
        用對方法才能瘦
        Coco薇(2016年2期)2016-03-22 02:42:52
        創(chuàng)衛(wèi)暗訪程序有待改進
        四大方法 教你不再“坐以待病”!
        Coco薇(2015年1期)2015-08-13 02:47:34
        賺錢方法
        中文在线天堂网www| 国产一区二区在三区在线观看| 亚洲精品国产综合久久| 国产乱码一区二区三区精品| 午夜精品久久久久久久99老熟妇| 久久婷婷人人澡人人喊人人爽| 丰满少妇大力进入av亚洲| 精品亚洲午夜久久久久| 激情内射亚洲一区二区| 极品美女调教喷水网站| 亚洲av无码国产精品永久一区| 真实国产老熟女粗口对白| 欧洲亚洲综合| 久久人人爽人人爽人人片av麻烦| 亚洲夜夜性无码| 午夜福利一区二区三区在线观看| 朝鲜女子内射杂交bbw| 午夜一级在线| 黄片在线观看大全免费视频| 中文字幕亚洲高清视频| 人妻熟妇乱又伦精品hd| 99热久久精里都是精品6| 北岛玲日韩精品一区二区三区| 国产诱惑人的视频在线观看| 国产午夜精品av一区二区麻豆| 国产精品香蕉在线观看| 亚洲狼人社区av在线观看| 中国黄色偷拍视频二区| 色偷偷久久久精品亚洲| 亚洲成av人片在线观看www| 美女扒开内裤让男生桶| 久久精品有码中文字幕1| 夜夜骚久久激情亚洲精品| 国产精品福利自产拍在线观看| 国产国拍亚洲精品mv在线观看| 啊v在线视频| 久久精品国产精品亚洲艾| 亚洲精品无码永久在线观看| 人人妻人人澡人人爽久久av| www.91久久| 99久久精品人妻一区二区三区|