4.2二叉樹的基本操作課件-浙教版高中信息技術(shù)選修1

4.2二叉樹的基本操作PART1二叉樹的建立一數(shù)組實(shí)現(xiàn)1.完全二叉樹從二叉樹的根節(jié)點(diǎn)開始，按從上而下、自左往右的順序?qū)個(gè)節(jié)點(diǎn)進(jìn)行編號(hào),根節(jié)點(diǎn)的編號(hào)為0，最后一個(gè)節(jié)點(diǎn)的編號(hào)為n-1。然后依次將二叉樹的節(jié)點(diǎn)用一組連續(xù)的數(shù)組元素來(lái)表示，節(jié)點(diǎn)編號(hào)與數(shù)組的下標(biāo)一一對(duì)應(yīng)。如圖甲所示的完全二叉樹所對(duì)應(yīng)的一維數(shù)組表示如圖乙所示。一數(shù)組實(shí)現(xiàn)2.非完全二叉樹

對(duì)于非完全二叉樹，先將它補(bǔ)全為一棵完全二叉樹，補(bǔ)上的節(jié)點(diǎn)及分支用虛線表示，如圖甲所示的一棵非完全二叉樹補(bǔ)全為圖乙所示的完全二叉樹。然后將補(bǔ)全后的完全二叉樹，從它的根節(jié)點(diǎn)開始,按從上而下、自左往右的順序?qū)個(gè)節(jié)點(diǎn)進(jìn)行編號(hào),根節(jié)點(diǎn)的編號(hào)為0，最后一個(gè)節(jié)點(diǎn)的編號(hào)為n-1。如圖丙所示，依次把完全二叉樹中原二叉樹的節(jié)點(diǎn)用一維數(shù)組的各個(gè)元素來(lái)表示，節(jié)點(diǎn)編號(hào)與數(shù)組的下標(biāo)一一對(duì)應(yīng)。若元素值為None，則節(jié)點(diǎn)為空節(jié)點(diǎn)。思考用數(shù)組表示的二叉樹的方式更適合完全二叉樹還是非完全二叉樹？為什么？

【例1】已知二叉樹T的形態(tài)如圖所示,則其對(duì)應(yīng)的一維數(shù)組表示為（

）練習(xí)A.bt=["A","B","C","D","E"]

B.bt=["A","B","C",None,"D",None,None,None,"E"]C.bt=["A","B","C",None,"D",None,None,None,None,"E"]D.bt=["A","B","C",None,"D",None,None,None,None,None,"E“]C練習(xí)A【舉一反三1】已知完全二叉樹T可用一維數(shù)組表示為bt=[“A”,“B”,“C”,“D”,“E”,“F”,“G”]，則節(jié)點(diǎn)C的父節(jié)點(diǎn)為

，左孩子節(jié)點(diǎn)為

，右孩子節(jié)點(diǎn)為

(選填:字母A~G)。FG二鏈表實(shí)現(xiàn)由于二叉樹的節(jié)點(diǎn)可能有兩個(gè)孩子，即左孩子和右孩子，因此二叉樹的節(jié)點(diǎn)至少需要3個(gè)域:一個(gè)數(shù)據(jù)域和兩個(gè)指針域。兩個(gè)指針域分別指向節(jié)點(diǎn)的左孩子和右孩子，這兩個(gè)指針?lè)謩e稱為左指針和右指針，這樣得到的鏈表也稱為二叉鏈表。如圖所示的是二叉樹及其對(duì)應(yīng)的二叉鏈表實(shí)現(xiàn)示意圖。左指針數(shù)據(jù)右指針三list實(shí)現(xiàn)用嵌套列表list來(lái)實(shí)現(xiàn)二叉樹（1）空樹用None表示（2）非空二叉樹用飽含三個(gè)元素的列表[d,l,r]表示，其中：d是根節(jié)點(diǎn)，r和l是左節(jié)點(diǎn)和右節(jié)點(diǎn)[“A”,,][“B”，“D”,“E”][“C”，None,None]二鏈表實(shí)現(xiàn)ABCGEIDFHList1=[‘A’,[‘B’,None,None],[‘C’,[‘D’,[‘F’,None,None],[‘G’,None,None]],[‘E’,[‘H’,None,None],[‘I’,None,None]]]]有如圖所示的二叉樹。用list表示該二叉樹為（

）練習(xí)A.[‘a(chǎn)’,’b’,’d’,’c’,’e’]B.[‘a(chǎn)’,[‘b’,[‘c’,None,None],None],[‘d’,[‘e’]]]C.[‘a(chǎn)’,[‘b’,[‘c’]],[‘d’,[‘e’,None,None]]]D.[‘a(chǎn)’,[‘b’,[‘c’,None,None]],[‘d’,[‘e’,None,None]]]Dabcde練習(xí)【例2】已知二叉樹T的形態(tài)如圖所示，則其對(duì)應(yīng)的嵌套列表為( ）A.bt=["'A",["B",["D",["E",None,None],None]],["C",None,None]]B.bt=["A",["B",None,["D",["E",None,None],None]],["C",None,None]]C.bt=["A",["'B",None,["D",["E",None,Non]],["C",None,None]]D.bt=["A",["B",None,["D",["E",None,None],None]],["C"]]B練習(xí)【舉一反三2】已知二叉樹T可用一維數(shù)組表示為bt=["A","B"，"C",None,"D","E","F"],請(qǐng)根據(jù)二叉樹的建立方法,回答下列問(wèn)題:(1)請(qǐng)繪制出二叉樹的形態(tài)圖。(2)請(qǐng)寫出該二叉樹list實(shí)現(xiàn)方法的嵌套列表bt=['A',['B',None,['D',None,None]],['C',['E',None,None],['F',None,None]]]PART2二叉樹的遍歷一前序遍歷規(guī)則：（中左右）先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹，最后訪問(wèn)右子樹。如右圖的前序遍歷順序?yàn)椋篈-B-D-H-E-C-F-I-G-J-KABCEGKFIJDH1245678910二中序遍歷規(guī)則：（左中右）先訪問(wèn)左子樹，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹。如右圖的中序遍歷順序?yàn)椋篋-H-B-E-A-I-F-C-J-G-K。ABCEGKFIJDH12345689107三后序遍歷規(guī)則：（左

右

中）先訪問(wèn)左子樹，再訪問(wèn)右子樹，最后訪問(wèn)根節(jié)點(diǎn)。如右圖的后序遍歷順序?yàn)椋篐-D-E-B-I-F-J-K-G-C-AABCEGKFIJDH12345689107三后序遍歷四二叉樹的基本操作

計(jì)算表達(dá)式和逆波蘭式用二叉樹表示例如：計(jì)算表達(dá)式：8-(3+2*6)/5+4

用二叉樹表示，如右圖。+-4532/+*86計(jì)算表達(dá)式：中序遍歷順序逆波蘭式：后序遍歷順序若用后序遍歷，則它的順序?yàn)椋?326*+5/-4+------逆波蘭式四二叉樹的基本操作1.二叉樹的唯一性例如：前序遍歷：E-A-C-B-D-G-F

中序遍歷：A-B-C-D-E-F-G

求其后序遍歷順序？先畫出二叉樹，再用后序遍歷規(guī)則求出其輸出順序后序遍歷：B-D-C-A-F-G-EEACBDGFABCDEFGEABCDFGGFABCDCBD四二叉樹的基本操作1.二叉樹的唯一性練習(xí)：

后序遍歷：H-D-E-B-I-F-J-K-G-C-A

中序遍歷：D-H-B-E-A-I-F-C-J-G-K

求其前序遍歷順序？

A-B-D-H-E-C-F-I-G-J-K四二叉樹的基本操作思考：前序遍歷序列和后序遍歷序列能否唯一確定一棵子樹？前序序列：A-B后序序列：B-AABAB練習(xí)A一棵二叉樹的先序遍歷序列為A-B-C-D-E-F,中序遍歷序列為C-BA-E-D-F,則后序遍歷序列為（

）A.A-C-B-E-DB.D-E-C-B-AC.D-E-A-B-CD.C-E-D-B-A練習(xí)B一棵二叉樹的前序遍歷序列是A-B-D-E-C-F-