資源簡介

(共37張PPT)
4
樹
第四章
A
B、C、D
A
B、C
H、I、J
3
2
3
6
7
3
4
樹與二叉樹
選擇性必修1《數據與數據結構》
第四章 樹
4.2 二叉樹的基本操作
二叉樹的建立
如何建立二叉樹？
可以用數組或者鏈表數據結構來實現！
如何存儲完全二叉樹與非完全二叉樹？
按層順序進行：先由第1層開始，依次到下一層，在每、一層中按照從左到右的順序創建節點。
二叉樹的建立
1.數組實現
編號：從二叉樹的根節點開始，按從上而下、自左往右的順序對n個節點進行編號。
根節點的編號為0，最后一個節點的編號為n-1
將二叉樹的節點用一組連續的數組元素來表示，節點編號與數組的下標一一對應。
（1）完全二叉樹
二叉樹的建立
（1）非完全二叉樹
先補全為一棵完全二叉樹，補上的節點及分支用虛線表示，如圖所示；
然后將補全后的完全二叉樹，對n個節點按序編號。
【從根節點開始，從上而下、自左往右，范圍[0,n-1]】
依次將原二叉樹的節點用一維數組的各個元素來表示，節點編號與數組的下標—―對應。
如何建立？
二叉樹的數組表示
A
C
B
A
C
B
如何用數組存儲此二叉樹？
數組下標 0 1 2 3 4 5 6
數組元素
A B C
二叉樹的建立
雖然，對完全二叉樹而言，一維數組的表示方式既簡單又節省存儲空間。
但對于一般二叉樹來說，采用一維數組表示時，結構雖然簡單，卻容易造成存儲空間的浪費。
一個深度為k，只有k個節點的樹，需要個節點的存儲空間才能表示出來。
2.鏈表實現
二叉樹的建立
二叉鏈表：
用任意一組存儲單元來存儲二叉樹的節點，用指向節點的指針來表示節點之間的關系。
二叉樹可能有兩個孩子【左孩子+右孩子】
因此二叉樹的節點至少需要3個域:一個數據域和兩個指針域。【左指針指向左孩子，右指針指向孩子】
拓展鏈接
二叉樹的list實現
二叉樹節點可以看成一個三元組，元素是左、右子樹和本節點數據。Python的list可以用于組合這樣的三個元素。下面介紹用list構造二叉樹的方法。
綜上，元組特點：
格式: ( , , , )
不可任意更改元素
元組是關系數據庫中的基本概念，關系是一張表，表中的每行，即數據庫中的每條記錄是一個元組，每列就是一個屬性，在二維表里，元組也稱為行。
元組和列表十分類似，只不過元組和字符串一樣是不可變的，即你不能修改元組，元組通過圓括號中用逗號分割的項目定義，元組通常用在使語句或用戶定義的函數能夠安全地采用一組值的時候，即被使用的元組的值不會改變。
拓展鏈接
二叉樹的list實現
二叉樹節點可以看成一個三元組，元素是左、右子樹和本節點數據。Python的list可以用于組合這樣的三個元素。下面介紹用list構造二叉樹的方法。
(1）空樹用None表示。
(2）非空二叉樹用包含三個元素的列表[d,l,r]表示，【d：根節點；l和r兩棵子樹】
[‘A’,[‘B’,’None’,’None’],
[‘C’,[’D’,[’F’,’None’,’None’],
[’G’,’None’,’None’]],
[’E’,[’H’,’None’,’None’],
[’I’,’None’,’None’]]]]
二叉樹的list實現
請將次二叉樹用list來表示：
[‘A’,’None’,
[’B’,[’C’,’None’,[’E’,’None’,’None’]],
[’D’,[’F’,’None’,’None’],’None’]]]
二叉樹的遍歷
圖形——直觀，但在計算機處理時，需要把非線性結構 線性序列，才能方便程序的實現。
通過二叉樹的遍歷即可，遍歷方式主要分為：前序遍歷、中序遍歷和后序遍歷等。
1.前序遍歷
規則:
若二叉樹為空，則空操作返回;
否則，根節點 左子樹 右子樹
前序遍歷順序為:A-B-D-H-E-C-F-I-G-J-K
二叉樹的遍歷
2.中序遍歷
規則:
若二叉樹為空，則空操作返回;
否則，左子樹 根節點 右子樹
中序遍歷順序為:D-H-B-E-A-I-F-C-J-G-K
注意事項！！！
如果選取其中一種遍歷策略對二叉樹進行遍歷，對于二叉樹的左右子樹，也需遵守該遍歷原則，即二叉樹的任意一個局部都必須遵守該遍歷原則。
3.后序遍歷
二叉樹的遍歷
規則:
若二叉樹為空，則空操作返回;
否則，左子樹 右子樹 根節點。
后序遍歷順序為:H-D-E-B-I-F-J-K-G-C-A
4.層序遍歷
二叉樹的遍歷
A
B
C
D
E
F
G
H
K
J
I
層序遍歷順序為: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一A
B.A一B一D一G一H一C一E一F
C.G一D一H一B一A一E一C一F
D.A一B一C一D一E一F一G一H
A
A
B
C
D
G
H
E
F
二叉樹的遍歷——數學表達式
中序遍歷[左—根—右]: 8-(3+2*6)/5+4 【中綴表達式】
后序遍歷:8 3 2 6*＋5 / - 4 + 【后綴表達式/逆波蘭表達式】
逆波蘭式的必要性：為確定運算順序，括號是必不可少的。
后綴表達式：因為采用了運算符緊跟在兩個操作數之后的方法，從而實現了無括號處理和優先級處理，使計算機的處理規則簡化為:從左到右依序完成計算。
二叉樹
？ 思考與練習
1.寫出如圖4.2.10所示的二叉樹的前序遍歷、中序遍歷、后序遍歷的結果。
前序遍歷：A B D E G H C F I J
中序遍歷：D B G E H A C I J F
后序遍歷：D G H E B J I F C A
二叉樹
？ 思考與練習
2.如果某二叉樹中有編號為1、2、3、4的四個節點,設計該二叉樹，使得其前序遍歷結果為1234，后序遍歷結果為4321。
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
二叉樹
如何確定唯一的二叉樹？
前序+中序？中序+后序？前序+后序？
前序遍歷【根—左—右】；中序遍歷【左—根—右】；后序遍歷【左—右—根】
前序+中序，中序+后序，均可確定唯一的一棵二叉樹！！！
前序 + 后序
【根—左—右】 【左—右—根】
雖然可確定唯一的根節點，但若左子樹/右子樹為空時，則無法確定該空子樹的位置！！！
選擇性必修1《數據與數據結構》
制作者：鄒修鴻
第四章 樹
4.3 抽象數據類型
二十一世紀外國語學校
抽象數據類型
數據類型是程序設計領域最重要的基本概念之一，它是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
有下列Python程序語句:
a=13 #語句1
b=10 #語句2
c=a+b #語句3
print(c)
語句1、語句2在給變量a和b分別賦值的同時也定義了兩個數據類型是整型的變量，而語句3中的“+”操作因為已經在整型類中已經定義，對于編程者來說，此時不必關心“+”操作的含義是如何讓計算機理解的。
4.3.1 數據類型與抽象數據類型
抽象數據類型
抽象是指抽取出事物具有的普遍性本質，是對具體事物的一個概括。
抽象是一種思考問題的方式，它隱藏了繁雜的細節，只保留實現目標所必需的信息，實現抽象化后有利于對事物的抽象，便于實現功能、提高模塊獨立性。
人們對已有數據類型進行抽象，就有了抽象數據類型。
抽象數據類型(ADT)是指一個數學模型及定義在該模型上的一組操作。
ADT的基本思想是抽象，只需作為一個整體來研究，而與其在計算機內部如何表示和實現無關。
str就是一個抽象數據類型，其操作都有明確的抽象意義，編程者不必受制于操作內部的具體實現技術，在程序設計時可以直接使用。
抽象數據類型
使用Python的內建函數時，編程者只需考慮函數的功能是否滿足實際需要，再確保函數調用時的表達式是否符合函數構造的要求，就可以使用此函數，而不需要知道該函數內部實現的任何具體細節。
4.3.2 數據類型的描述
抽象數據類型
描述抽象數據類型描述如下：
ADT 抽象數據類型名：
Data
數據元素之間邏輯關系的定義
Operation
操作1
初始條件
操作結果描述
操作2
……
操作n
……
endADT
！！！
4.3.2 數據類型的描述
線性表抽象數據類型
ADT List：
List(self) #創建一個新表
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在表中第一次出現的位置
forall(self,op) #對表中的每個元素執行op操作
4.3.3 抽象數據類型的作用
抽象數據類型主要體現了程序設計中問題分解、抽象和信息隱藏的特征。
把問題分解成多個規模較小且容易處理的問題，將每個功能模塊作為一個獨立單元，隱藏具體的實現過程，通過一次或多次的模塊調用來實現整個問題的解決。
好處：
使用抽象數據類型編寫出來的程序結構清晰、層次分明，便于程序正確性的證明和復雜性的分析;
因為其模塊化的特點，在程序設計中容易糾正，具有很好的可維護性;由于抽象數據類型的表示和實現都可以封裝起來，便于移植和重用;
因為算法設計與數據結構設計的隔開，降低了算法和程序設計的復雜度，有助于在開發過程中少出差錯，保證編寫的程序有較高的可靠性，
同時，允許數據結構的自由選擇，給了算法的優化空間，提高了程序運行的效率。
！！！
拓 展 鏈 接
簡單字符處理ADT
ADT String:
String(self,sseq) #基于字符序列sseq建立一個字符串
is_empty(self) #判斷本字符串是否為空
len(self) #取得字符串的長度
char(self,index) #取得字符串中位置index的字符
substr(self,a,b) #取得字符串中[a:b]的子串，左閉右開區間
match(self,string) #查找串string在本字符串中第一次出現的位置
concat(self,string) #獲得本字符串與另一個字符串string的拼接串
subst(self,str1,str2) #獲得將本字符串中的子串str1替換成str2的結果串
拓 展 鏈 接
隊列抽象數據類型ADT
ADT Queue:
Queue(self) #創建空隊列
is_empty(self) #判斷隊列是否為空，空時返回True，否則返回False
enqueue(self,elem) #將元素elem加入隊列，即入隊
dequeue(self) #刪除隊列里最早進的元素并將其返回，即出隊
peek(self) #查看隊列里最早進入的元素，不刪除
拓 展 鏈 接
二叉樹抽象數據類型
ADT BinTree: #一個二叉樹抽象數據類型
Bin Tree(self,data,left,right) #構造操作，創建一個新二叉樹
is_empty(self) #判斷self是否為一個空二叉樹
num_nodes(self) #求二叉樹的節點個數
data(self) #獲得二叉樹根節點存儲的數據
left(self) #獲得二叉樹的左子樹
right(self) #獲得二叉樹的右子樹
set_left(self,btree) #用btree取代原來的左子樹
set_right(self,btree) #用btree取代原來的右子樹
traversal(self) #遍歷二叉樹中各節點數據的迭代器
forall(self,op) #對二叉樹中的每個節點的數據中op操作
建樹
二叉樹的遍歷
數據類型與抽象數據類型
抽象數據類型的描述及其作用
課堂小結
學習評價
對自己和同伴的表現進行客觀的評價，并思考后續完善的方向。（5=優秀，4=超出一般水平，3=滿意，2=有待改進，1=不太理想）
評分項 自我評價 同學互評
能從新課導入中的感知建樹的方式 5 4 3 2 1 5 4 3 2 1
能理解樹的前序遍歷 5 4 3 2 1 5 4 3 2 1
能自主學習樹的中序遍歷和后序遍歷，并能模擬出相應的遍歷序列 5 4 3 2 1 5 4 3 2 1
能了解抽象數據類型，以及描述某種抽象數據類型和它的作用。 5 4 3 2 1 5 4 3 2 1
課堂作業
1.思考教材“問題與討論”中的兩個問題。
謝謝觀看
制作者：XXXXXX

展開更多......

收起↑