二叉樹的基本操作 課件 【考點(diǎn)打靶+定向訓(xùn)練】 浙教版（2019）高中信息技術(shù)選修1

4.2二叉樹的基本操作無論是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)數(shù)據(jù)，都需要對數(shù)據(jù)元素逐個(gè)進(jìn)行組織存儲和處理。二叉樹的基本操作，主要包括二叉樹的建立和遍歷等。二叉樹的建立1.建立二叉樹的操作，可以按照層的順序進(jìn)行，先由第1層開始，依次到下一層，在每一層中按照從左到右的順序創(chuàng)建節(jié)點(diǎn)。二叉樹的建立可以用數(shù)組或者鏈表數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。1.數(shù)組實(shí)現(xiàn)用數(shù)組來表示二叉樹時(shí)，分為以下兩種情況。（1）完全二叉樹從二叉樹的根節(jié)點(diǎn)開始，按從上而下、自左向右的順序?qū)個(gè)節(jié)點(diǎn)進(jìn)行編號，根節(jié)點(diǎn)的編號為0，最后一個(gè)節(jié)點(diǎn)的編號為n-1。然后依次將二叉樹的節(jié)點(diǎn)用一組連續(xù)的數(shù)組元素來表示，節(jié)點(diǎn)編號與數(shù)組的下標(biāo)一一對應(yīng)。如下圖中圖甲所示的完全二叉樹所對應(yīng)的一維數(shù)組表示如圖乙所示。ABCDE甲完全二叉樹ABCDE01234567乙數(shù)組表示示意圖（2）非完全二叉樹對于非完全二叉樹，先將它補(bǔ)充為一棵完全二叉樹，補(bǔ)上的節(jié)點(diǎn)及分支用虛線表示，如下圖圖甲所示的一棵非完全二叉樹補(bǔ)全為圖乙所示的完全二叉樹。然后將補(bǔ)全后的完全二叉樹，從它的根節(jié)點(diǎn)開始，按從上而下、自左往右的順序?qū)個(gè)節(jié)點(diǎn)進(jìn)行編號，根節(jié)點(diǎn)的編號為0，最后一個(gè)節(jié)點(diǎn)的編號為n-1。如圖丙所示，依次把完全二叉樹中原二叉樹的節(jié)點(diǎn)用一維數(shù)組的各個(gè)元素來表示，節(jié)點(diǎn)編號與數(shù)組的下標(biāo)一一對應(yīng)。ABCABC甲原二叉樹乙補(bǔ)全后的二叉樹01234567丙數(shù)組實(shí)現(xiàn)示意圖ABC對于完全二叉樹而言，一維數(shù)組的表示方式既簡單又節(jié)省存儲空間。但對于一般的二叉樹來說，采用一維數(shù)組表示時(shí)，結(jié)構(gòu)雖然簡單，卻容易造成存儲空間的浪費(fèi)。如圖甲所示，一個(gè)深度為k且只有k個(gè)節(jié)點(diǎn)的樹需要如圖乙所示2k-1個(gè)節(jié)點(diǎn)的存儲空間才能表示出來。2.鏈表實(shí)現(xiàn)二叉樹也可以采用鏈表來實(shí)現(xiàn)，用任意一組存儲單元來存儲二叉樹的節(jié)點(diǎn)，用指向節(jié)點(diǎn)的指針來表示節(jié)點(diǎn)之間的關(guān)系。由于二叉樹的節(jié)點(diǎn)可能有兩個(gè)孩子，即左孩子和右孩子，因此二叉樹的節(jié)點(diǎn)至少需要3個(gè)域：一個(gè)數(shù)據(jù)域和兩個(gè)指針域。兩個(gè)指針域分別指向節(jié)點(diǎn)的左孩子和右孩子，這兩個(gè)指針分別稱為左指針和右指針，這樣得到的鏈表也稱為二叉鏈表。如下圖所示的是二叉樹及其對應(yīng)的二叉鏈表實(shí)現(xiàn)示意圖。ABDCEFGA頭指針B^C^^D^E^F^^G^二叉樹的list實(shí)現(xiàn)二叉樹節(jié)點(diǎn)可以看成是一個(gè)三元組，元素是左、右子樹和本節(jié)點(diǎn)數(shù)據(jù)。Python的list可以用于組合這樣的三個(gè)元素。下面介紹用list構(gòu)造二叉樹的方法。（1）空樹用None表示。（2）非空二叉樹用包含三個(gè)元素的列表[d,l,r]表示，其中：d表示根節(jié)點(diǎn)的元素，l和r是兩棵子樹，采用與整個(gè)二叉樹同樣結(jié)構(gòu)的list表示。這樣就可以把二叉樹映射到一種分層的list結(jié)構(gòu)，每棵二叉樹都有與之對應(yīng)的（遞歸結(jié)構(gòu)的）list。ABCDFGEHI[‘A’,[‘B’,None,None],[‘C’,[‘D’,[‘F’,None,None],[‘G’,None,None]],[‘E’,[‘H’,None,None],[‘I’,None,None]]]]二叉樹的遍歷在完成二叉樹的建立操作后，就可以對二叉樹的各個(gè)節(jié)點(diǎn)進(jìn)行訪問，即遍歷操作。二叉樹的遍歷，是指按照一定的規(guī)則和次序訪問二叉樹中的所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)都被訪問一次且僅被訪問一次。按照不同的遍歷方式對節(jié)點(diǎn)進(jìn)行訪問，其處理效率不完全相同。二叉樹的遍歷方式有很多，主要有前序遍歷、中序遍歷和后序遍歷等。1.前序遍歷前序遍歷的規(guī)則是：若二叉樹為空，則空操作返回；否則，先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹。ABDEHCFIGJK前序遍歷順序?yàn)椋篈-B-D-H-E-C-F-I-G-J-K2.中序遍歷中序遍歷的規(guī)則是：若二叉樹為空，則空操作返回；否則，先訪問左子樹，再訪問根節(jié)點(diǎn)，最后訪問右子樹。ABDEHCFIGJK中序遍歷順序?yàn)椋篋-H-B-E-A-I-F-C-J-G-K3. 后序遍歷后序遍歷的規(guī)則是：若二叉樹為空，則空操作返回；否則，先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點(diǎn)。ABDEHCFIGJK后序遍歷順序?yàn)椋篐-D-E-B-I-F-J-K-G-C-A如果選取其中一種遍歷策略對二叉樹進(jìn)行遍歷，對于二叉樹的左右子樹，也需遵守該遍歷原則，即二叉樹的任意一個(gè)局部都必須遵守該遍歷原則。對一棵二叉樹進(jìn)行前序遍歷時(shí)，根節(jié)點(diǎn)總是處于遍歷序列之首；中序遍歷時(shí)根節(jié)點(diǎn)位置居中，左子樹的所有節(jié)點(diǎn)都在其左邊，右子樹的所有節(jié)點(diǎn)都在其右邊；后序遍歷時(shí)根節(jié)點(diǎn)位置在最后，其所有節(jié)點(diǎn)都在其左邊。二叉樹的應(yīng)用如果將數(shù)學(xué)表達(dá)式中的運(yùn)算數(shù)和運(yùn)算符視為二叉樹的每個(gè)節(jié)點(diǎn)，那么可以構(gòu)造出各種表達(dá)式樹。+-84/5+3*26中序遍歷：8-(3+2*6)/5+4中綴表達(dá)式后序遍歷：8326*+5/-4+后綴表達(dá)式（逆波蘭表達(dá)式）計(jì)算機(jī)的處理規(guī)則簡化為：從左到右依序完成計(jì)算，并方便求得結(jié)果。已知前序遍歷序列和后序遍歷序列，能否唯一確定一棵二叉樹？不能。假如將一棵二叉樹看成由根節(jié)點(diǎn)與左、右子樹（子節(jié)點(diǎn)）組成，根據(jù)前序遍歷和后序遍歷序列都可找到根節(jié)點(diǎn)，但當(dāng)左、右子樹（子節(jié)點(diǎn)）有一個(gè)為空時(shí)，則無法確定序列中的其他節(jié)點(diǎn)到底是位于左子樹還是右子樹。例如，某二叉樹的根節(jié)點(diǎn)下僅有一個(gè)子節(jié)點(diǎn)，只知道前序遍歷與后序遍歷，是無法確定該子節(jié)點(diǎn)到底是右子節(jié)點(diǎn)還是左子節(jié)點(diǎn)。練一練1.有如圖所示的二叉樹。用list表示該二叉樹為：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]]]abcdeD2.表達(dá)式（3+5）*4-8/2的后綴表達(dá)式為：A.35+4*-82/B.35+4*8-2/C.35+4*82-/D.35+4*82/-D3.一棵二叉樹的前序遍歷序列是abdecfhg，后序遍歷序列是debhfgca，則根節(jié)點(diǎn)