42二叉樹(shù)的基本操作課件高二上學(xué)期選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第四章浙教版

4.2二叉樹(shù)的基本操作《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》一、二叉樹(shù)的建立1.一維數(shù)組實(shí)現(xiàn)–完全二叉樹(shù)ABCDE01234567ABCDE01234bt=[“A”,“B”,“C”,“D”,“E”]按自上而下、自左向右的順序?qū)個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)是0，最后節(jié)點(diǎn)是n-1。一、二叉樹(shù)的建立ACB0123456ABC01234561.一維數(shù)組實(shí)現(xiàn)–非完全二叉樹(shù)bt=[“A”,None,“B”,None,None,None,“C”]練習(xí)：綠本P41例1補(bǔ)全為一棵完全二叉樹(shù)None：表示空節(jié)點(diǎn)一、二叉樹(shù)的建立1.一維數(shù)組實(shí)現(xiàn)ABCDE0123456ABCDEACB0123456ABC對(duì)于完全二叉樹(shù)，一維數(shù)組的表達(dá)方式簡(jiǎn)單又節(jié)省空間。對(duì)于非完全二叉樹(shù)，一維數(shù)組的表達(dá)方式雖然簡(jiǎn)單，卻容易造成存儲(chǔ)空間的浪費(fèi)。一、二叉樹(shù)的建立重要結(jié)論：建議做個(gè)筆記0123456ABCDE下標(biāo)為i的節(jié)點(diǎn)的孩子節(jié)點(diǎn)的下標(biāo)為左孩子：右孩子：2*i+12*i+2下標(biāo)為i的節(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)為非根節(jié)點(diǎn)i>0(i-1)//2ABCDE01234i2*1+12*1+2i(3-1)//2=一、二叉樹(shù)的建立2.鏈表實(shí)現(xiàn)ABCDEFG由二叉樹(shù)定義可知，二叉樹(shù)的每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，即左孩子和右孩子。因此，可將節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)數(shù)據(jù)域和兩個(gè)指針域。兩個(gè)指針域分別指向節(jié)點(diǎn)的左孩子和右孩子，這兩個(gè)指針?lè)謩e稱為左指針和右指針。左孩子指針數(shù)據(jù)域右孩子指針lchilddatarchild一、二叉樹(shù)的建立2.鏈表實(shí)現(xiàn)ABCDEGFAB∧C∧E∧D∧頭指針∧G∧∧F∧如圖所示，是將左圖的二叉樹(shù)采用鏈表結(jié)構(gòu)存儲(chǔ)，這種鏈表也稱為二叉鏈表。∧代表“無(wú)后繼指針”拓展鏈接二叉樹(shù)的list（列表）實(shí)現(xiàn)

二叉樹(shù)節(jié)點(diǎn)可以看成一個(gè)三元組，元素是左、右子樹(shù)和本節(jié)點(diǎn)數(shù)據(jù)。Python的列表可以用于構(gòu)造這樣的三元組，可以使用嵌套列表來(lái)模擬二叉樹(shù)，非空二叉樹(shù)可以用包含三個(gè)元素的列表[data,left,right]來(lái)表示每一個(gè)節(jié)點(diǎn)，其中data是根節(jié)點(diǎn)的元素，left和right是兩棵子樹(shù)，空樹(shù)或空節(jié)點(diǎn)用None表示。ABCDEGFHI[‘A’,[‘B’,None,None],[‘C’,[‘D’,[‘F’,None,None],[‘G’,None,None]],

[‘E’,[‘H’,None,None],

[‘I’,None,None]]]]練習(xí)：綠本P41例2二、二叉樹(shù)的遍歷（重難點(diǎn)內(nèi)容）二叉樹(shù)的遍歷是指按照一定的規(guī)則和次序依次訪問(wèn)二叉樹(shù)中的所有節(jié)點(diǎn)，使得所有節(jié)點(diǎn)都被訪問(wèn)有且僅有一次。遍歷的方式前序遍歷根

左

右中序遍歷左

根

右后序遍歷左

右

根主要看根節(jié)點(diǎn)是什么時(shí)候遍歷二、二叉樹(shù)的遍歷1.前序遍歷規(guī)則：根

左

右1、若所在二叉樹(shù)為空，則空操作返回；2、先訪問(wèn)根節(jié)點(diǎn)3、再訪問(wèn)左子樹(shù)4、再訪問(wèn)右子樹(shù)ABCDEGFHIKJ二、二叉樹(shù)的遍歷1.前序遍歷:根

左

右（1）整個(gè)樹(shù)遍歷：A/

B/C/（2）A左子樹(shù)遍歷：B/D/E/（3）B左子樹(shù)遍歷：D/None/H（4）B右子樹(shù)遍歷：E/None/None（5）A左子樹(shù)遍歷：B-D-H-E（6）整個(gè)樹(shù)遍歷：A/B-D-H-E

/

C/（7）整個(gè)樹(shù)遍歷：A/

B-D-H-E

/

C-F-I-G-J-K/ABCDEGFHIKJ根左右BDEH左根右DH左根前序遍歷的順序?yàn)椋篈-B-D-H-E-C-F-I-G-J-K建議：補(bǔ)齊二叉樹(shù)二、二叉樹(shù)的遍歷2.中序遍歷：左

根

右ABCDEGFHIKJ根左右（1）整個(gè)樹(shù)遍歷：

/A/

/

（2）A左子樹(shù)遍歷：

/B//（3）B左子樹(shù)遍歷：None/D/H（4）B右子樹(shù)遍歷：None/E/None（5）A左子樹(shù)遍歷：D-H-B-E（6）整個(gè)樹(shù)遍歷：D-H-B-E/A//（7）整個(gè)樹(shù)遍歷：D-H-B-E/A/I-F-C-J-G-K中序遍歷的順序?yàn)椋篋-H-B-E-A-I-F-C-J-G-K二、二叉樹(shù)的遍歷3.后序遍歷:左

右

根后序遍歷的順序?yàn)椋篐-D-E-B-I-F-J-K-G-C-AABCDEGFHIKJ根左右二、二叉樹(shù)的遍歷–課堂練習(xí)ABCDEGFIHJ前序遍歷：中序遍歷：后序遍歷：A-B-D-H-I-E-C-F-J-GH-D-I-B-E-A-J-F-C-GH-I-D-E-B-J-F-G-C-A三、遍歷二叉樹(shù)的應(yīng)用1

–表達(dá)式樹(shù)中綴表達(dá)式（中序遍歷）：8-(3+2*6)/5+48/-4++53*26構(gòu)造表達(dá)式樹(shù)，運(yùn)算數(shù)作為葉子節(jié)點(diǎn)，運(yùn)算符都是分支(根)節(jié)點(diǎn)。后綴表達(dá)式（后序遍歷）：8326*+5/-4+逆波蘭表達(dá)式已知某二叉樹(shù)的前序（根左右）遍歷為A-B-D-H-I-E-C-F-G，中序（左根右）遍歷為H-D-I-B-E-A-F-C-G,請(qǐng)繪制二叉樹(shù)形態(tài)示意圖，寫(xiě)出后序（左右根）遍歷為序列，思考二叉樹(shù)是否唯一。后序遍歷為：H-I-D-E-B-F-G-C-A三、遍歷二叉樹(shù)的應(yīng)用2：推導(dǎo)出第三種遍歷序列

ABCDGEFIH綠本P42第3題已知某二叉樹(shù)的后序（左右根）遍歷為G-D-H-E-B-I-F-C-A，中序（左根右）遍歷為D-G-B-E-H-A-C-I-F,請(qǐng)繪制二叉樹(shù)形態(tài)示意圖，寫(xiě)出前序（根左右）遍歷序列，思考二叉樹(shù)是否唯一。前序遍歷為：A-B-D-G-E-H-C-F-I三、遍歷二叉樹(shù)的應(yīng)用2：推導(dǎo)出第三種遍歷序列

ABCDGEFHI二、二叉樹(shù)的遍歷已知某二叉樹(shù)的前序遍歷為A-B-D-C-E-F-G，后序遍歷為D-B-F-E-G-C-A,請(qǐng)繪制二叉樹(shù)形態(tài)示意圖，寫(xiě)出中序遍歷序列，思考二叉樹(shù)是否唯一。ABCDG