




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、二叉樹的記憶結(jié)構(gòu)和掃描,二叉樹的掃描,二叉樹的記憶結(jié)構(gòu),總結(jié)和工作,順序記憶,二叉樹表,三叉表,連鎖記憶,問題的提出,遞歸掃描算法,掃描的應用例子,1,PPT學習交流,二叉樹的順序記憶,順序記憶用一系列的連續(xù)存儲手段存儲數(shù)據(jù),順序記憶要求數(shù)據(jù)是線性結(jié)構(gòu)2、PPT學習交流,二叉樹的順序記憶:a,c,g,b,d,e,f,k,l,h,m,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,滿二叉樹: PPT學習交流二叉樹的順序記憶,012345678910121315,數(shù)組的后綴也是節(jié)點的編號,01234567891011315,4,PPT學習交流,二叉樹的順序記憶,完全二叉樹:
2、從上到下,從左依次編號01、2、3、4、5、6、9、5 一般二叉樹:設想完全二叉樹,0、0、0、0、0、0、0、0、0、6,PPT學習交流,二叉樹的順序記憶,0、0、0、0、0、0、0、0、1、2、3、4、5、6、7、8、9、10 11、12、12 、8、PPT學習交流、#define MAX_TREE_SIZE 100 /二叉樹的最大節(jié)點數(shù)typedeftelemtypesqbitreemax _ tree _ size; /1號小區(qū)存儲根節(jié)點SqBiTree bt; 二叉樹順序記憶,9,PPT學習交流,#define MAX_TREE_SIZE 100 /二叉樹的最大節(jié)點數(shù)typedefs
3、tructtelemtypedatamax _ tree _ size; char flagMAX_TREE_SIZE; SqBiTree; 二叉樹順序記憶、一般二叉樹、10、PPT學習交流、鏈存儲二叉樹、二叉樹的節(jié)點結(jié)構(gòu):左指針區(qū)域、指向當前節(jié)點的左子葉、數(shù)據(jù)區(qū)域、指向當前節(jié)點的值信息、右指針區(qū)域、指向當前節(jié)點的右子葉、二叉樹的根節(jié)點的頭指針: 上述二叉樹的二叉樹的二叉樹如下:a,f,e,c,d,b,root,鏈存儲二叉鏈表,12,PPT學習通信,typedef struct BiTNode /節(jié)點結(jié)構(gòu)t elemtype d struct BiTNode *lchild、*rchild;
4、/左右兒童指針BiTNode、*BiTree; 節(jié)點結(jié)構(gòu):二叉鏈表的c語言類型:左指針域、數(shù)據(jù)域、右指針域、鏈存儲二叉鏈表、13、PPT學習通信、三叉鏈表的節(jié)點結(jié)構(gòu):到父母節(jié)點數(shù)據(jù)域,右指針域,連鎖存儲三叉鏈表,14,PPT學習通信,root,二叉樹的三叉鏈表,連鎖存儲,15,PPT學習交流,typedefstructtritrit 結(jié)構(gòu)節(jié)點*rchild、*rchild; 結(jié)構(gòu)節(jié)點* parent; 三叉樹,*三叉樹;三叉鏈表的c語言類型為:節(jié)點結(jié)構(gòu):/節(jié)點結(jié)構(gòu),/左右孩子的指針,/父母的指針,鏈中記憶三叉鏈表,16,PPT學習交流,問題的提案在實用上經(jīng)常需要尋找具有二叉樹特征的節(jié)點17、P
5、PT學習交流、問題的提案、定義:通過沿某個搜索路徑訪問二叉樹中的節(jié)點,各節(jié)點只被訪問一次,而且只被訪問一次。 作用:掃描的目的是線性化,使二叉樹中的節(jié)點按某種順序排列成一個線性矩陣,便于處理。18、PPT學習交流、問題的提出、線性結(jié)構(gòu)的掃描:因為每個節(jié)點只有一個接班人,所以搜索路徑只有一個。 二叉樹的掃描:二叉樹不是非線性結(jié)構(gòu),如果每個節(jié)點有兩個后續(xù),就存在如何掃描,用什么樣的搜索路徑掃描的問題。、19、PPT學習交流、問題的提出、二叉樹存在以下三個搜索路徑: 1先追溯上下層次,從2左(子樹)到右(子樹)的掃描DLR、LDR、LRD 3接在右(子樹)之后掃描左(子樹)。 DRL、RDL、RLD
6、、20、PPT學習交流,先通過順序(根),再通過、根、左子樹、右子樹,二叉樹為空樹則為空的操作; 否則,(1)訪問根節(jié)點(2)先橫穿左子樹(3),再橫穿右子樹,21,PPT,學習交流, 首先橫穿a、b、c、d、e、g、h、k、a、f、g、h、k、h、22、PPT學習交流、班級23 PPT學習交流,void Preorder (BiTree T,void(*visit)(TElemType /右子樹),先巡回,24,PPT學習交流,中序(根)巡回,左子樹,根,左子樹,右否則,(1)按中順序遍歷左子樹(2)訪問根節(jié)點(3)中順掃描右子樹,25,PPT學習交流:中順(根)掃描,a,b,c,d,e,f
7、,g,k,a,b,c,d,e,f,f void(*visit)(TElemType /橫穿右子樹,27,PPT學習交流,后序(根)橫穿左子樹,右子樹,根,根,左子樹,右子樹,二叉樹為空樹則空操作; 否則,(1)后遍歷左子樹(2)后遍歷右子樹(3)訪問根節(jié)點。28、PPT學習通信、后手(根)遍歷、a、b、c、d、e、f、g、h、k、a、dc、b、h、g、fe、29、PPT學習通信、語音信箱寫出PPT學習交流,教室練習三種掃描的結(jié)果,31,PPT學習交流,序文序列:中文序列:后文序列:ABBCDDEGHKF,D C B H K G F E A,三種掃描的比較,32,PPT學習交流,1,visit,
8、不考慮三種掃描的算法3種導線的比較,2、3種導線的執(zhí)行過程不同(visit的位置不同)。 3、前序列和中序列,或者可以從后序列和中序列唯一確定的二叉樹,33,PPT學習交流,前序列:中序列:后序列:A B C D E F G H K,bbcehgkf,dbchkgfea,三種掃描的比較,34,PPT學習交流,3,復制二叉樹4,制作二叉樹檢查具有二叉樹的節(jié)點,應用示例,累計1、二叉樹的節(jié)點數(shù),35,PPT學習交流,只訪問各節(jié)點一次,設定全局變量count=0,累計二叉樹的節(jié)點數(shù),visit為:count,36 t )返回、計數(shù); preorder (t-lchild ) preorder (t-
9、rchild )、void Preorder (BiTree T,* visit ) (t elemtype/遍歷右子樹,37,PPT學習交流,收集二叉樹中的節(jié)點數(shù)、主()、預覽器(t )、打印(“% d”、計數(shù));38、PPT學習交流、遞歸思想:如果是空樹,則返回0,計算二叉樹中的節(jié)點數(shù),求出左分樹的節(jié)點數(shù)m,求出右分樹的節(jié)點數(shù)n,返回mn1,39,PPT學習交流,計算二叉樹中的節(jié)點數(shù),int count node (bi tree 返回指針t指向的二叉樹中所有葉的節(jié)點的數(shù)量,22222222222222 T ) return 0 /空樹,m=CountNode(T-lchild ),n=C
10、ountNode(T-rchild ),return (m n 1)、40, 求二叉樹的深度,課程練習:空樹的深度為0,41,PPT學習交流,求二叉樹的深度,返回int Depth (BiTree T )/二叉樹的深度,if (! t )返回(0)、深度左側(cè)=深度,深度右側(cè)=深度,深度val=1? 深度左:深度右; 返回深度val; 42、PPT學習通信,檢查具有二叉樹的節(jié)點,給二叉樹的根節(jié)點指針t和x,在t中查找數(shù)據(jù)元素值等于x的節(jié)點,如果找到,則返回指針,否則返回空指針。t,X=C,43,PPT學習通信,查詢二叉樹中的某個節(jié)點,1 .在二叉樹不空閑的前提下,與根節(jié)點的要素進行比較,相等的話
11、找到指向根節(jié)點的指針,2 .否則用左子樹搜索,找到的話返回指針如果找到,則返回指針,否則返回空指針,44,PPT學習通信,在二叉樹中的某個節(jié)點,BiTree Search (BiTree T,TElemType x ),if (! t )如果返回(空) if (t -數(shù)據(jù)=x )返回(t ),if(p) /返回值不是空指針,則在左側(cè)子樹中x表示返回(p ); else return (搜索(t-rchild,x ) );p=Search(T-lchild,x )、45、PPT學習交流,復制二叉樹(練習),給定的一個二叉樹,t指向其根節(jié)點,復制一個二叉樹,返回指向新的根節(jié)點的指針,根元素、右子樹
12、,NEWT,左子樹、右子樹、左子樹、46、PPT學習交流,復制二叉樹,1,t為空的話復制空指針、2、根節(jié)點,p指向新的節(jié)點,復制左子樹,pl指向左子樹的根,4,復制右子樹,pr復制右子樹的根回到6,p,47,PPT學習交流,復制二叉樹,比特樹復制,AD (! t )返回(空),p=新bi節(jié)點; p -數(shù)據(jù)=t -數(shù)據(jù),pl=復制(t-lchild ),pr=復制(t-rchild ),p-lchild=pl; p-rchild=pr; PS (p )、48、PS學習交流,用以下字符串表示, 創(chuàng)建、二叉樹,并以字符串形式在“根左子樹右子樹”中定義一棵二叉樹,用空白字符表示,1 )空樹,2 )只包
13、含根節(jié)點的二叉樹,a、用字符串“a”表示,3 )、49、PPT學習交流,二叉樹,AB C D,a,a ,50,PPT學習交流,制作二叉樹,生成Status CreateBiTree(BiTree /根節(jié)點,return OK; PK (! (t=新比特)退出(溢出)、if (ch=) T=NULL; 建立CreateBiTree(T-lchild) /左子樹,bitree(t-rcild) /結(jié)構(gòu)右子樹,51,PPT學習交流,總結(jié),1 )二叉樹的順序記憶表示,2 )二叉樹的二叉鏈表記憶表示,二叉鏈表,父母鏈表,三叉鏈表、后序(后根)、52,PPT學習交流,作業(yè),作業(yè): 6.12,6.42,6.43,53,PPPT學習交流建立二叉樹,由二叉樹的先序和中序序列建立樹,二叉樹的中序序列:左子樹,左子樹,右子樹,右子樹,根,根建立二叉樹,ab,be,gf,ab,be,f,g,a,b,c,c,c,d,d,e,f,g,a,b,c,d,d,e,f,f,g,g,先著3:55, PPT學習通信、二叉樹、bi node * bi tree :30創(chuàng)建(TPR,T in,int prepos,int low,int
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 《按群計數(shù)》幼兒園課件
- 【遼陽石化財務管理問題及對策分析7100字】
- 湖南省邵陽市隆回縣2022-2023學年八年級下學期期中考試數(shù)學答案
- 如何編制安全考試題目及答案
- 百科常識考試題及答案
- 安環(huán)專員考試題目及答案
- 2025年撫順物理中考試題及答案
- 2025年飛行員理論知識考試試題及答案
- 2025年持續(xù)健康教育與個人發(fā)展能力測試試題及答案
- 汽修廠財務報表合并校驗一致性規(guī)定
- 人教版九年級化學上冊暑假銜接講義(初二升初三)
- 部編版四年級語文上冊《全冊》課件
- 跆拳道館技術(shù)崗位薪酬制度
- 國內(nèi)外嬰幼兒早期教育的現(xiàn)狀與發(fā)展分析
- 無人駕駛車法規(guī)-深度研究
- 康復科實習生入科培訓
- 《寧晉縣國土空間總體規(guī)劃(2021-2035年)》
- 2024年度乳腺癌篩查與早期診斷課件
- 2024年學校師德師風培訓課件:培育有溫度的教育者
- 體育產(chǎn)業(yè)智能賽事管理系統(tǒng)開發(fā)計劃
- 工業(yè)自動化設備維護保養(yǎng)操作手冊
評論
0/150
提交評論