課程名稱數(shù)據(jù)結(jié)構(gòu)11

1、課程名稱 數(shù)據(jù)結(jié)構(gòu) 11 授課題目遍歷二元樹的算法授課日期2003 年 11 月 5 日授課班級生物醫(yī)學工程授課時數(shù)4授課方式理論課授課重點、難點1. 掌握遍歷二元樹與線性表之間的關(guān)系2. 掌握三種遍歷方法3. 熟悉遞歸與非遞歸遍歷的各自特點。授課內(nèi)容、教具與時間分配授課內(nèi)容、教具與時間分配遍歷二元樹 遍歷：是指按一定的規(guī)律訪問該結(jié)構(gòu)的所有結(jié)點，而且對每個結(jié)點只訪問一次。遍歷二元樹是按一定的規(guī)律將二元樹中的結(jié)點排成一個線性序列，得到二元樹中結(jié)點的先根序列、中根序列和后根序列。實際上這是對一個非線性結(jié)構(gòu)進行線性化，使每個結(jié)點（除序列中第一個結(jié)點和最后一個結(jié)點外）在線性序列中有且僅有一個直接前驅(qū)結(jié)

2、點和一個直接后繼結(jié)點。1.遍歷二元樹的三種方法根據(jù)二元樹的遞歸定義，一棵非空二元樹由根結(jié)點，左子樹和右子樹組成。因此，遍歷一棵非空二元樹的問題可分解為三個子問題： 訪問根結(jié)點 ，遍歷左子樹 ， 和 遍歷右子樹 分別用字母 D L R 表示 。 可以排出六種方安： 第一組： DLR ， LDR ， LRD root 第二組： DRL ， RDL ， RLD A 兩組對稱，可只討論第一組。 DLR 先根（前根、先序、前序）順序遍歷 preorder B CLDR 中根（中序） 順序遍歷 inorderLRD 后根（后序） 順序遍歷 postorder先根遍歷： 若二元樹空，root=NULL,返回

3、。 若二元樹非空，則訪問根結(jié)點，按先根遍歷左子樹（遞歸），按先根遍歷右子樹（遞歸）。中根遍歷： 若二元樹空，root=NULL,返回。 若二元樹非空，則按先根遍歷左子樹（遞歸），訪問根結(jié)點，按先根遍歷右子樹（遞歸）。后根遍歷： 若二元樹空，root=NULL,返回。若二元樹非空，則按先根遍歷左子樹（遞歸），按先根遍歷右子樹（遞歸），訪問根結(jié)點，。以P.70 圖為例，圖解三種遍歷方法。root 是指向根結(jié)點的指針，是該二元樹的標識。 root 授課內(nèi)容、教具與時間分配小結(jié)、復習、思考題、參考書思考題：1. 執(zhí)行 p72 recursive.c ，將圖 1 (p.70 圖 4.5) 以前根字符序列輸入，執(zhí)行結(jié)果存入數(shù)據(jù)文件 recursive.r1 ，觀察結(jié)果。再用手工方法做前根、中根和后根遍歷，驗證結(jié)果。2. 執(zhí)行 recursive.c ，將圖 2 (思考題) 以前根字符序列輸入，執(zhí)行結(jié)果存入數(shù)據(jù)文件，觀察結(jié)果。再用手工方法做前根、中根和后根遍歷，驗證結(jié)果。4. 執(zhí)行