<wbr id="ede8e"></wbr><bdo id="ede8e"><var id="ede8e"><optgroup id="ede8e"></optgroup></var></bdo>
    1. <sub id="ede8e"></sub>
    2. <sub id="ede8e"></sub>
    3. 18禁无遮挡啪啪无码网站,真人无码作爱免费视频,2018年亚洲欧美在线v,国产成人午夜一区二区三区 ,亚洲精品毛片一区二区,国产在线亚州精品内射,精品无码国产污污污免费,国内少妇人妻偷人精品
      首頁 > 文章中心 > 正文

      二叉樹還原

      前言:本站為你精心整理了二叉樹還原范文,希望能為你的創作提供參考價值,我們的客服老師可以幫助你提供個性化的參考范文,歡迎咨詢。

      摘要:通過對同一棵二叉樹三種遍歷方式的分析,概括出由前序、中序或由中序、后序遍歷結果快速還原二叉樹的方法。

      關鍵詞:二叉樹;二叉樹的遍歷;二叉排序樹;還原

      二叉樹是最為常用的數據結構,它的實際應用非常廣泛。二叉樹的遍歷方式有三種,前序遍歷、中序遍歷、后序遍歷。先序遍歷的順序為:NLR,即先根結點,然后左子樹、右子樹;中序遍歷順序為:LNR先左子樹,然后根結點、右子樹;后序遍歷順序為:LRN先左子樹、然后右子樹、根結點。由前序和中序遍歷、由中序和后序遍歷序列可以唯一確定一棵二叉樹,而由前序和后序遍歷序列不能唯一確定一棵二叉樹。

      二叉排序樹對二叉樹作了進一步的限定:根結點的權值大于(或小于)左子樹中所有結點的權值;根結點的權值小于(或大于)其右子樹中所有結點的權值。

      那么如何根據三種遍歷序列之間的關系及二叉排序樹來快速還原一棵二叉樹?下面以二叉樹的前序和中序遍歷序列為基礎,利用二叉排序樹的性質,給出快速還原二叉樹的方法。

      1由給定前序和中序序列或中序和后序序列還原二叉樹的方法

      例:前序序列:ABDECFGH中序序列:DEBACGFH(后序序列:EDBGHFCA)

      (1)給中序序列中的每個結點從小到大、從左到右賦以權值,如下:

      D(1)E(2)B(3)A(4)C(5)G(6)F(7)H(8)

      (2)還原時讀入的序列為前序序列,從左到右依次讀入序列中的各個結點值和相應的權值;

      (3)由讀入的序列,根據第1)步中給定的權值按照二叉排序樹的構造規則構造二叉排序樹。第一個讀入的結點為根結點,其他結點分別為左右子樹中的結點。設根結點為TT,權值為NN,當前讀入結點為SS,權值為MM,若MM(4)將SS插入到TT的左子樹或右子樹的過程中,仍然遵循3)中的規則,直至左子樹或右子樹為空時止。

      (5)讀入序列結束時,二叉樹還原成功。還原后的二叉樹如下圖。

      (6)對于由中序序列和后序序列還原二叉樹是,讀入的序列為后序序列,從右向左讀入,構造規則同上。還原結果與上述結果完全一致。2還原方法的確定依據

      二叉樹遍歷過程中,在中序序列中,根結點的左子樹中的所有結點都在根結點的左側,根結點的右子樹中的所有結點都在根結點的右側,這個特點恰好與二叉排序樹具有相同的性質;在讀入序列時,前序序列則從左向右讀,這恰好與遍歷二叉樹的順序相同;后序序列從右向左讀,則按照根結點、右子樹、左子樹的順序還原。

      (1)設二叉樹共有N個結點(N為大于1的正整數),我們按照還原方法給中序序列中的這N個結點分別賦予權值1,2…N,設根結點的權值為M(1(2)由二叉樹的遍歷規則可知,權值為1,2…M-1的結點為根結點的左子樹中的結點,而權值為M+1,…N的結點為根結點的右子樹中的結點。

      (3)將這N個結點劃分成3個子集AA=(1,2…M-1)BB=(M)CC=(M+1,…N),由于前序序列第一個讀入的結點必定為二叉根的根結點,所以BB為根結點,AA集為左子樹,CC集為右子樹。

      (4)同理不斷讀入前序序列中的結點,依次遞歸還原BB對應的左子樹和CC對應的右子樹,最后將三棵子樹合并成以BB為根結點、AA的根結點為BB的左子樹、CC的根結點為BB的右子樹的一棵二叉排序樹。

      (5)同理可以得出,由中序序列和后序序還原二叉樹的規則也成立。

      (6)在還原過程中,讀入序列的順序也遵循也先根結點,后子樹的規律。

      3總結

      在二叉樹的一些應用中,如平衡二叉樹、紅黑樹等,常常要觀察二叉樹的形態,對其進行判斷并調整。根據遍歷序列和二叉排序樹的性質快速還原出二叉樹對于研究相關的問題有很大的幫助。

      參考文獻

      [1]嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社,1996

      文檔上傳者
      主站蜘蛛池模板: 精品国产中文字幕在线| 日韩熟女乱综合一区二区| 国内精品极品久久免费看| 亚洲精品自拍视频在线看| 亚洲国产午夜福利精品| 国产美女精品自在线拍免费| 日本另类αv欧美另类aⅴ| 丝袜美腿亚洲综合在线观看视频| 天堂在线精品亚洲综合网| 九九热在线观看免费视频| 国产盗摄xxxx视频xxxx| 亚洲欧美日韩综合一区在线 | 国产色悠悠在线免费观看| 国产边摸边吃奶边叫做激情视频| 成人区人妻精品一区二区| 国产一区二区在线有码| 免费无码又爽又刺激高潮虎虎视频 | 日韩精品福利视频在线观看| 无码高潮爽到爆的喷水视频app| 青青青爽在线视频观看| 成年无码av片在线蜜芽| 国产男女黄视频在线观看| 亚洲国产精品第一二三区| 国产二区三区不卡免费| 亚洲一区二区经典在线播放| 免费超爽大片黄| 国产精品尤物午夜福利| 丰满人妻被黑人连续中出| 国产精品粉嫩嫩在线观看| 日韩有码国产精品一区| 日本精品aⅴ一区二区三区| 日韩精品中文字幕一线不卡| 福利一区二区在线观看| 无码一区二区三区AV免费| 国产av无码国产av毛片| 人妻系列无码专区免费| 日韩丝袜亚洲国产欧美一区| 国内自拍偷拍福利视频看看| 精品一区二区亚洲国产| 国产成人精品18| 日本一区二区三区视频一|