4.2二叉樹操作4.3抽象數(shù)據(jù)類型課件浙教版高中信息技術(shù)選修1

4樹第四章AB、C、DAB、CH、I、J3236734樹與二叉樹選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》制作者：鄒修鴻第四章樹4.2二叉樹的基本操作二叉樹的建立如何建立二叉樹？可以用數(shù)組或者鏈表數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)！如何存儲完全二叉樹與非完全二叉樹？按層順序進行：先由第1層開始，依次到下一層，在每、一層中按照從左到右的順序創(chuàng)建節(jié)點。二叉樹的建立1.數(shù)組實現(xiàn)編號：從二叉樹的根節(jié)點開始，按從上而下、自左往右的順序?qū)個節(jié)點進行編號。

根節(jié)點的編號為0，最后一個節(jié)點的編號為n-1將二叉樹的節(jié)點用一組連續(xù)的數(shù)組元素來表示，節(jié)點編號與數(shù)組的下標一一對應(yīng)。（1）完全二叉樹二叉樹的建立（1）非完全二叉樹先補全為一棵完全二叉樹，補上的節(jié)點及分支用虛線表示，如圖所示；然后將補全后的完全二叉樹，對n個節(jié)點按序編號?！緩母?jié)點開始，從上而下、自左往右，范圍[0,n-1]】

依次將原二叉樹的節(jié)點用一維數(shù)組的各個元素來表示，節(jié)點編號與數(shù)組的下標—―對應(yīng)。如何建立？二叉樹的數(shù)組表示ACBACB如何用數(shù)組存儲此二叉樹？數(shù)組下標0123456數(shù)組元素ABC二叉樹的建立

2.鏈表實現(xiàn)二叉樹的建立二叉鏈表：用任意一組存儲單元來存儲二叉樹的節(jié)點，用指向節(jié)點的指針來表示節(jié)點之間的關(guān)系。二叉樹可能有兩個孩子【左孩子+右孩子】因此二叉樹的節(jié)點至少需要3個域:一個數(shù)據(jù)域和兩個指針域?！咀笾羔樦赶蜃蠛⒆?，右指針指向孩子】拓展鏈接二叉樹的list實現(xiàn)

二叉樹節(jié)點可以看成一個三元組，元素是左、右子樹和本節(jié)點數(shù)據(jù)。Python的list可以用于組合這樣的三個元素。下面介紹用list構(gòu)造二叉樹的方法。綜上，元組特點：格式:(

,

,

,)不可任意更改元素元組是關(guān)系數(shù)據(jù)庫中的基本概念，關(guān)系是一張表，表中的每行，即數(shù)據(jù)庫中的每條記錄是一個元組，每列就是一個屬性，在二維表里，元組也稱為行。元組和列表十分類似，只不過元組和字符串一樣是不可變的，即你不能修改元組，元組通過圓括號中用逗號分割的項目定義，元組通常用在使語句或用戶定義的函數(shù)能夠安全地采用一組值的時候，即被使用的元組的值不會改變。拓展鏈接二叉樹的list實現(xiàn)

二叉樹節(jié)點可以看成一個三元組，元素是左、右子樹和本節(jié)點數(shù)據(jù)。Python的list可以用于組合這樣的三個元素。下面介紹用list構(gòu)造二叉樹的方法。(1）空樹用None表示。(2）非空二叉樹用包含三個元素的列表[d,l,r]表示，【d：根節(jié)點；l和r兩棵子樹】[‘A’,[‘B’,’None’,’None’],[‘C’,[’D’,[’F’,’None’,’None’],[’G’,’None’,’None’]],[’E’,[’H’,’None’,’None’],[’I’,’None’,’None’]]]]二叉樹的list實現(xiàn)請將次二叉樹用list來表示：[‘A’,’None’,[’B’,[’C’,’None’,[’E’,’None’,’None’]],[’D’,[’F’,’None’,’None’],’None’]]]二叉樹的遍歷圖形——直觀，但在計算機處理時，需要把非線性結(jié)構(gòu)

線性序列，才能方便程序的實現(xiàn)。通過二叉樹的遍歷即可，遍歷方式主要分為：前序遍歷、中序遍歷和后序遍歷等。1.前序遍歷規(guī)則:若二叉樹為空，則空操作返回;否則，根節(jié)點左子樹右子樹前序遍歷順序為:A-B-D-H-E-C-F-I-G-J-K二叉樹的遍歷2.中序遍歷規(guī)則:若二叉樹為空，則空操作返回;否則，左子樹根節(jié)點右子樹中序遍歷順序為:D-H-B-E-A-I-F-C-J-G-K注意事項?。?！如果選取其中一種遍歷策略對二叉樹進行遍歷，對于二叉樹的左右子樹，也需遵守該遍歷原則，即二叉樹的任意一個局部都必須遵守該遍歷原則。3.后序遍歷二叉樹的遍歷規(guī)則:若二叉樹為空，則空操作返回;否則，左子樹右子樹根節(jié)點。后序遍歷順序為:H-D-E-B-I-F-J-K-G-C-A4.層序遍歷二叉樹的遍歷ABCDEFGHKJI層序遍歷順序為:A-B-C-D-E-F-G-H-I-J-K二叉樹的遍歷——習題1.請寫出下列二叉樹的四種遍歷順序：二叉樹的遍歷——習題例2.已知二叉樹T的前序遍歷序列為A一B一D一G一H一C一E一F，中序遍歷序列是G一D一H一B一A一E一C一F,則其后序遍歷序列是()A.G一H一D一B一E一F一C一AB.A一B一D一G一H一C一E一FC.G一D一H一B一A一E一C一FD.A一B一C一D一E一F一G一H

AABCDGHEF二叉樹的遍歷——數(shù)學表達式中序遍歷[左—根—右]:8-(3+2*6)/5+4【中綴表達式】后序遍歷:8326*＋5/-4+

【后綴表達式/逆波蘭表達式】逆波蘭式的必要性：為確定運算順序，括號是必不可少的。后綴表達式：因為采用了運算符緊跟在兩個操作數(shù)之后的方法，從而實現(xiàn)了無括號處理和優(yōu)先級處理，使計算機的處理規(guī)則簡化為:從左到右依序完成計算。二叉樹？

思考與練習1.寫出如圖所示的二叉樹的前序遍歷、中序遍歷、后序遍歷的結(jié)果。前序遍歷：ABDEGHCFIJ中序遍歷：DBGEHACIJF后序遍歷：DG

H

E

B

J

I

F

C

A二叉樹？

思考與練習2.如果某二叉樹中有編號為1、2、3、4的四個節(jié)點,設(shè)計該二叉樹，使得其前序遍歷結(jié)果為1234，后序遍歷結(jié)果為4321。1234123412341234二叉樹如何確定唯一的二叉樹？前序+中序？中序+后序？前序+后序？前序遍歷【根—左—右】；中序遍歷【左—根—右】；后序遍歷【左—右—根】前序+中序，中序+后序，均可確定唯一的一棵二叉樹！??！前序

+

后序【根—左—右】【左—右—根】雖然可確定唯一的根節(jié)點，但若左子樹/右子樹為空時，則無法確定該空子樹的位置?。?！選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》制作者：鄒修鴻第四章樹4.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型數(shù)據(jù)類型是程序設(shè)計領(lǐng)域最重要的基本概念之一，它是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。有下列Python程序語句:a=13#語句1b=10

#語句2c=a+b#語句3print(c)語句1、語句2在給變量a和b分別賦值的同時也定義了兩個數(shù)據(jù)類型是整型的變量，而語句3中的“+”操作因為已經(jīng)在整型類中已經(jīng)定義，對于編程者來說，此時不必關(guān)心“+”操作的含義是如何讓計算機理解的。4.3.1數(shù)據(jù)類型與抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象是指抽取出事物具有的普遍性本質(zhì)，是對具體事物的一個概括。抽象是一種思考問題的方式，它隱藏了繁雜的細節(jié)，只保留實現(xiàn)目標所必需的信息，實現(xiàn)抽象化后有利于對事物的抽象，便于實現(xiàn)功能、提高模塊獨立性。人們對已有數(shù)據(jù)類型進行抽象，就有了抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型(ADT)是指一個數(shù)學模型及定義在該模型上的一組操作。ADT的基本思想是抽象，只需作為一個整體來研究，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。str就是一個抽象數(shù)據(jù)類型，其操作都有明確的抽象意義，編程者不必受制于操作內(nèi)部的具體實現(xiàn)技術(shù)，在程序設(shè)計時可以直接使用。抽象數(shù)據(jù)類型使用Python的內(nèi)建函數(shù)時，編程者只需考慮函數(shù)的功能是否滿足實際需要，再確保函數(shù)調(diào)用時的表達式是否符合函數(shù)構(gòu)造的要求，就可以使用此函數(shù)，而不需要知道該函數(shù)內(nèi)部實現(xiàn)的任何具體細節(jié)。4.3.2數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述如下：ADT抽象數(shù)據(jù)類型名：Data

數(shù)據(jù)元素之間邏輯關(guān)系的定義Operation

操作1

初始條件

操作結(jié)果描述

操作2 ……

操作n ……endADT?。?！4.3.2數(shù)據(jù)類型的描述線性表抽象數(shù)據(jù)類型ADTList： List(self)#創(chuàng)建一個新表 is_empty(self)#判斷self是否為一個空表 len(self)#返回表的長度 prepend(self,elem)#在表頭插入元素elem append(self,elem)#在表尾插入元素elem insert(self,elem,i)#在表的第i位置插入元素elem del_first(self)#刪除第一個元素 del_last(self)#刪除最后一個元素 search(self,elem)#查找元素elem在表中第一次出現(xiàn)的位置 forall(self,op)#對表中的每個元素執(zhí)行op操作4.3.3抽象數(shù)據(jù)類型的作用抽象數(shù)據(jù)類型主要體現(xiàn)了程序設(shè)計中問題分解、抽象和信息隱藏的特征。把問題分解成多個規(guī)模較小且容易處理的問題，將每個功能模塊作為一個獨立單元，隱藏具體的實現(xiàn)過程，通過一次或多次的模塊調(diào)用來實現(xiàn)整個問題的解決。好處：使用抽象數(shù)據(jù)類型編寫出來的程序結(jié)構(gòu)清晰、層次分明，便于程序正確性的證明和復雜性的分析;因為其模塊化的特點，在程序設(shè)計中容易糾正，具有很好的可維護性;由于抽象數(shù)據(jù)類型的表示和實現(xiàn)都可以封裝起來，便于移植和重用;因為算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)設(shè)計的隔開，降低了算法和程序設(shè)計的復雜度，有助于在開發(fā)過程中少出差錯，保證編寫的程序有較高的可靠性，同時，允許數(shù)據(jù)結(jié)構(gòu)的自由選擇，給了算法的優(yōu)化空間，提高了程序運行的效率。?。?！拓展鏈接簡單字符處理ADTADTString: String(self,sseq)#基于字符序列sseq建立一個字符串 is_empty(self)#判斷本字符串是否為空 len(self)#取得字符串的長度 char(self,index)#取得字符串中位置index的字符 substr(self,a,b)#取得字符串中[a:b]的子串，左閉右開區(qū)間 match(self,string)#查找串string在本字符串中第一次出現(xiàn)的位置 concat(self,string)#獲得本字符串與另一個字符串string的拼接串 subst(self,str1,str2)#獲得將本字符串中的子串str1替換成str2的結(jié)果串拓展鏈接隊列抽象數(shù)據(jù)類型ADTADTQueue: Queue(self)#創(chuàng)建空隊列 is_empty(self)#判斷隊列是否為空，空時返回True，否則返回False enqueue(self,elem)#將元素elem加入隊列，即入隊 dequeue(self)#刪除隊列里最早進的元素并將其返回，即出隊 peek(self)#查看隊列里最早進入的元素，不刪除拓展鏈接二叉樹抽象數(shù)據(jù)類型ADTBinTree:#一個二叉樹抽象數(shù)據(jù)類型 BinTree(self,data,left,right)#構(gòu)造操作，創(chuàng)建一個新二叉樹

is_empty(self)#判斷self是否為一個空二叉樹 num_nodes(self)#求二叉樹的節(jié)點個數(shù) data(self)#獲得二叉樹根節(jié)點存儲的數(shù)據(jù) left(self)#獲得二叉樹的左子樹 right(self)