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

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

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

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

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

左

右中序遍歷左

根

右后序遍歷左

右

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

左

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

左

右（1）整個樹遍歷：A/

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

/

C/（7）整個樹遍歷：A/

B-D-H-E

/

C-F-I-G-J-K/ABCDEGFHIKJ根左右BDEH左根右DH左根前序遍歷的順序為：A-B-D-H-E-C-F-I-G-J-K建議：補齊二叉樹二、二叉樹的遍歷2.中序遍歷：左

根

右ABCDEGFHIKJ根左右（1）整個樹遍歷：

/A/

/

（2）A左子樹遍歷：

/B//（3）B左子樹遍歷：None/D/H（4）B右子樹遍歷：None/E/None（5）A左子樹遍歷：D-H-B-E（6）整個樹遍歷：D-H-B-E/A//（7）整個樹遍歷：D-H-B-E/A/I-F-C-J-G-K中序遍歷的順序為：D-H-B-E-A-I-F-C-J-G-K二、二叉樹的遍歷3.后序遍歷:左

右

根后序遍歷的順序為：H-D-E-B-I-F-J-K-G-C-AABCDEGFHIKJ根左右二、二叉樹的遍歷–課堂練習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三、遍歷二叉樹的應(yīng)用1

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

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

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