計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(郵電)1-6.ppt

1、1,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),課件,第一章 數(shù)據(jù)結(jié)構(gòu),第二章 操作系統(tǒng),第三章 軟件工程,第四章 數(shù)據(jù)庫,2,第一章 數(shù)據(jù)結(jié)構(gòu),第一單元,第二單元,第三單元,第四單元,第五單元,第六單元,第七單元,第八單元,3,樹、森林與二叉樹的轉(zhuǎn)換,第六單元,第一章 數(shù)據(jù)結(jié)構(gòu),4,1.3.3 二叉樹的遍歷,所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。 訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。 “訪問”的意思對結(jié)點(diǎn)施行某些操作。 例：輸入結(jié)點(diǎn)的信息、修改結(jié)點(diǎn)的數(shù)據(jù)值等。（但要求這種訪問不破壞它原來的數(shù)據(jù)結(jié)

2、構(gòu)）,遍歷的規(guī)則 從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，對于任一給定結(jié)點(diǎn)，可以按某種次序執(zhí)行三個(gè)操作： （1）訪問結(jié)點(diǎn)本身(N)， （2）遍歷該結(jié)點(diǎn)的左子樹(L)， （3）遍歷該結(jié)點(diǎn)的右子樹(R)。 以上三種操作有六種執(zhí)行次序：NLR、LNR、LRN、NRL、RNL、RLN。, 設(shè)訪問根結(jié)點(diǎn)記作 N 遍歷根的左子樹記作 L 遍歷根的右子樹記作 R 則可能的遍歷次序有 前序 NLR 鏡像 NRL 中序 LNR 鏡像 RNL 后序 LRN 鏡像 RLN,5,一遍歷算法 (Inorder Traversal) 1中序遍歷的遞歸算法定義： 若二叉樹非空，

3、則依次執(zhí)行如下操作： (1)遍歷左子樹； (2)訪問根結(jié)點(diǎn)； (3)遍歷右子樹。,例：表達(dá)式語法樹 遍歷結(jié)果: a + b * c - d - e / f,表達(dá)式 a + b * (c d ) e / f 對應(yīng)的語法樹,6,采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則中序遍歷算法可描述為： void InOrder(BinTree T) if(T) / 如果二叉樹非空 InOrder(T-lchild)； printf(c，T-data) / 訪問結(jié)點(diǎn) InOrder(T-rchild); / InOrder,7,例：表達(dá)式語法樹 遍歷結(jié)果 - + a * b - c d / e f,表達(dá)式 a + b *

4、(c d ) e / f 對應(yīng)的語法樹,2先序遍歷的遞歸算法定義： 若二叉樹非空，則依次執(zhí)行如下操作： 前序遍歷二叉樹算法的框架是 若二叉樹為空，則空操作； 否則 (1) 訪問根結(jié)點(diǎn)； (2) 遍歷左子樹； (3) 遍歷右子樹。,8,例：表達(dá)式語法樹 遍歷結(jié)果 a b c d - * + e f / -,表達(dá)式 a + b * (c d ) e / f 對應(yīng)的語法樹,3后序遍歷的遞歸算法定義： 若二叉樹非空，則依次執(zhí)行如下操作： 后序遍歷二叉樹算法的框架是 若二叉樹為空，則空操作； 否則 (1)遍歷左子樹； (2)遍歷右子樹； (3)訪問根結(jié)點(diǎn)。,9,二遍歷序列 1遍歷二叉樹的執(zhí)行蹤跡,圖1-

5、50遍歷二叉樹的搜索路線,10,例:右圖,得到的中序序列為： D B A E C F,2.遍歷序列 (1)中序序列 中序遍歷二叉樹時(shí)，對結(jié)點(diǎn)的訪問次序?yàn)橹行蛐蛄小?(2)先序序列 先序遍歷二叉樹時(shí)，對結(jié)點(diǎn)的訪問次序?yàn)橄刃蛐蛄小?例:上圖，得到的先序序列為： A B D C E F,11,三 二叉鏈表的構(gòu)造 1. 基本思想 基于先序遍歷的構(gòu)造，即以二叉樹的先序序列為輸入構(gòu)造。,(3)后序序列 后序遍歷二叉樹時(shí)，對結(jié)點(diǎn)的訪問次序?yàn)楹笮蛐蛄小?例:右圖, 得到的后序序列為： D B E F C A,例: 建立上圖所示二叉樹，其輸入的先序序列是：ABD CE F 。,12,2 構(gòu)造算法 假設(shè)虛結(jié)點(diǎn)輸入

6、時(shí)以空格字符表示，相應(yīng)的構(gòu)造算法為: void CreateBinTree (BinTree *T) /構(gòu)造二叉鏈表。T是指向根指針的指針, /故修改*T就修改了實(shí)參(根指針)本身 char ch； if(ch=getchar()=) *T=NULL； /讀入空格，將相應(yīng)指針置空 else,13, /讀入非空格 *T=(BinTNode *) malloc(sizeof(BinTNode)； /生成結(jié)點(diǎn) (*T)-data=ch； CreateBinTree( 否則R2為R1的右子樹的根結(jié)點(diǎn)。 R3, , Rn結(jié)點(diǎn)的插入方法同上。 例:對于一組關(guān)鍵字51,34,79,18,45,86， 生成對應(yīng)的二叉排序樹的過程如圖158所示。,38,例:對于一組關(guān)鍵字51,34,79,18,45,86,39,小結(jié) 需要復(fù)習(xí)的知識(shí)點(diǎn), 二叉樹的遍歷 遍歷算法 中序遍歷的遞歸算法定義 先序遍歷的遞歸算法定義 后序遍歷的遞歸算法定義 遍歷序列 遍歷二叉樹的執(zhí)行蹤跡 遍歷序列 中序序列 先序序