軟件技術(shù)基礎(chǔ)課件3——數(shù)據(jù)結(jié)構(gòu)與算法2)

1、Shanghai Jiao Tong University1第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p線性表堆棧（Stack）：一種特殊的線性表，其插入與刪除運算都只在線性表的一端進行 一端封閉，不允許進行插入與刪除元素（棧底棧底） 另一端開口，允許插入與刪除元素（棧頂棧頂） 順序存儲結(jié)構(gòu)下，插入與刪除運算不需要移動表中其他數(shù)據(jù)元素 棧底元素總是最后被插入，最先能被刪除 棧頂元素最先被插入，最后才能被刪除素p堆棧的操作原則： “先進后出”（first in last out，F(xiàn)ILO） “后進先出”（last in first out，LIFO）p堆棧應(yīng)用場合

2、：需要先進后出的情形 手電筒裝電池、子彈裝入彈夾 二叉樹遍歷時的臨時量存儲Shanghai Jiao Tong University2第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p堆棧的順序存儲 一維數(shù)組S（l m）作入棧退棧作為棧的順序存儲空間，其中m為棧的最大容量Shanghai Jiao Tong University3第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p堆棧的基本運算 入棧：在棧頂位置插入一個新元素 將棧頂指針進1（即top+1） 將新元素插入到棧頂指針指向的位置注：當棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明棧

3、空間已滿，不能再進行入棧操作（上溢出） 退棧：取出棧頂元素并賦給一個指定的變量 將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量 將棧頂指針退1（即 top1）注：當棧頂指針為0時，說明棧空，不可能進行退棧操作（下溢出） 讀棧頂元素：將棧頂元素賦給一個指定的變量 不改變棧頂指針 若棧頂指針為空，則說明堆棧已空Shanghai Jiao Tong University4第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p堆棧的基本運算 3種基本運算：入棧、退棧與讀棧頂元素容量10 9 8 7 top 6 F 5 E 4 D 3 C 2 B bottom 1 A 10 9

4、 top 8 Y 7 X 6 F 5 E 4 D 3 C 2 B bottom 1 A 10 9 8 top 7 X 6 F 5 E 4 D 3 C 2 B bottom 1 A Shanghai Jiao Tong University5第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p線性表隊列（Queue）：允許在一端進行插入、而在另一端進行刪除的線性表 允許插入的一端稱為隊尾隊尾，用一個稱為尾指針（rear）的指向隊尾元素，即尾指針總是指向最后被插入的元素； 允許刪除的一端稱為隊頭隊頭p隊列的操作原則： “先進先出”（first in first out，F(xiàn)I

5、FO）p隊列應(yīng)用場合：需要先進先出的情形 機床的指令隊列 計算機操作系統(tǒng)的程序排隊Shanghai Jiao Tong University6第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p隊列的存儲常用一維數(shù)組作為隊列的順序存儲空間表 預先分配一段連續(xù)的存儲空間 入隊操作進改變尾指針位置 退隊操作僅改變頭指針位置p隊列的運算 向隊列的隊尾插入一個元素入隊入隊運算 從隊列的排頭刪除一個元素退隊退隊運算 front A B C rear D front B C rear D front A B C D rear E Shanghai Jiao Tong Univers

6、ity7第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p循環(huán)隊列循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，隊列循環(huán)使用 普通隊列存在的問題 若隊尾元素已占據(jù)存儲空間的最底部，則無法進行入隊操作 循環(huán)隊列中，當存儲空間最底位置被占用時，只要存儲空間最頂位置空閑，便可將元素加入到第一個位置，即將存儲空間最頂位置為隊尾 用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素Shanghai Jiao Tong Universi

7、ty8第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p循環(huán)隊列的運算 入隊入隊運算 退隊退隊運算 判斷循環(huán)隊列是否為空： rear=(front+1)%m； rear=front；但空隊列和滿隊列時均出現(xiàn)首尾指針指向同一位置！#define QueSize 100Typedef char DataType;Typedef Struct int front; int rear; int count; DataType dataQueSize; cirque;Shanghai Jiao Tong University9第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表

8、數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p循環(huán)隊列的運算置空：void EmptyQue (cirque *q) q-front=q-rear=0; q-count=0;判斷隊列是否空：int IfQueEmpty (cirque *q) if q-coount=0 return 1; else return 0;Shanghai Jiao Tong University10第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p循環(huán)隊列的運算判斷隊列是否為滿：int IfQueFull (cirque *q) if q-coount= QueSize return 1; else retu

9、rn 0;入隊操作：void EnterQue (cirque *q, DataType x ) if(IfQueFull (q) error(“overflow!”); q-count+; q-dataq-rear=x; q-rear=(q-rear+1)% QueSize ;Shanghai Jiao Tong University11第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法線性表數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)p循環(huán)隊列的運算出隊操作：DataType DepartQue (cirque *q) DataType temp; If QueEmpty(q) error(“underflow!”

10、); temp=q-dataq-front; q-count-; q-rear=(q-rear+1)% QueSize ; return temp;Shanghai Jiao Tong University12第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法串結(jié)構(gòu)串結(jié)構(gòu)p概念：由 0 個或多個字符組成的有限序列 通常記為：s =“ a1 a2 a3 ai an ” ( n0 ) 必須有“”，引號不是串的內(nèi)容，但必須存在，以此避免與變量名或數(shù)的常量混淆 S串名 a1 a2 a3 ai an串值x 的值為整數(shù) 6027。 x 的值為字符串 6027。 例：x = “6027” x = 6027tes

11、t =“test” Shanghai Jiao Tong University13第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法串結(jié)構(gòu)串結(jié)構(gòu)p空串：空串：不含任何字符的串，串長度 = 0，用符號 表示。 p空格串：一個或多個空格組成的串p子串：由串中任意個連續(xù)的字符組成的子序列p主串：包含子串的串p位置：字符在序列中的序號 子串在主串中的位置是子串的首字符在主串中的位置p串相等：長度相等且各個對應(yīng)位置的字符都相等 p舉例： S=“Link16” S1=“n”、S2=“NA”、S=“Link16” 子串。S4=“Lk6” 非子串（非串 S 中的連續(xù)字符所組成）。在 S 中的位置：3 在 S 中的

12、位置：1 串是任意串的子串，任意串是其自身的子串。 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法串結(jié)構(gòu)串結(jié)構(gòu)p串的邏輯結(jié)構(gòu)：串的邏輯結(jié)構(gòu)：與線性表相似 ，區(qū)別是串的數(shù)據(jù)對象約定是字符集p串的基本操作：與線性表不同，其復雜程度高于線性表 在線性表的基本操作中，大多以“單個元素”作為操作對象 在串的基本操作中，通常以“串的整體”作為 操作對象 例如： 在串中查找某個子串、求 取一個子串、在串的某個位置上插入一個子 串以及刪除一個子串等 五種最操 作：串賦值 StrAssign、串比較 StrCompare、求串長 StrLength、串聯(lián)

13、接 Concat、求子串 SubStringShanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法串結(jié)構(gòu)串結(jié)構(gòu)p串的表達：串的表達：存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu) 類似，但組成串的結(jié)點是單個字符p串的兩種表示方法：串的兩種表示方法： 隱式表達：在串之后加入一個串的結(jié)束標志。如 C 中使用 “0”，“0” 不計入串長 顯式表達：首地址顯式地記錄串的長度 T h i s i s a d o g . 0 14 T h i s i s a d o g . Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算

14、法串結(jié)構(gòu)串結(jié)構(gòu)p串的存儲串的存儲： 定長順序存儲：也稱為靜態(tài)存儲分配的順序串。用一組的存儲單元來串中的字符序列 若串的實際長度超過定長，則被“截斷” 堆分配存儲：仍以一組空間足夠大的、地址連續(xù)的存儲單元依次存放串值字符序列，但它們的存儲空間是在程序執(zhí)行過程中如：C 語言中提供的串類型即為這種存儲方式。動態(tài)分配函數(shù) malloc ( ) 分配一塊實際串長所需要的存儲空間 “堆”），如果分配成功，則返回此空間的起始地址，作為串的基址。由 free( ) 函數(shù)釋放串不再需要的空間Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法串結(jié)構(gòu)串結(jié)構(gòu)p串的

15、存儲串的存儲： 鏈串存儲結(jié)構(gòu)：單鏈表存放字符串，簡稱為。與單鏈表的差異只是它的便于串的插入和刪除操作，但是空間利用率不高 塊鏈存儲結(jié)構(gòu)：為了提高空間的利用率，可以使每個結(jié)點存放多個字符（和的折衷）S ABCDE S ABCDES A B CD E # Shanghai Jiao Tong University18第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 樹型結(jié)構(gòu)（非線性結(jié)構(gòu)） 結(jié)點之間有分支 具有層次關(guān)系 例 自然界：樹 人類社會 家譜 軍隊組織結(jié)構(gòu)計算機領(lǐng)域 編譯：用樹表示源程序的語法結(jié)構(gòu) 數(shù)據(jù)庫系統(tǒng)：用樹組織信息 算法分析：用樹描述執(zhí)行過程 行政組織機構(gòu) 集團軍 步2師步1師 炮兵旅

16、 裝甲師 3團 1團 雷達營 1營3營 偵察連防空旅2團 炮團2營 炮連Shanghai Jiao Tong University19第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p定義（遞歸定義）：樹 (Tree) 是 n (n0) 個結(jié)點的有限集。若 n = 0，稱 為空樹；若 n 0，則它滿足如下兩個條件： (1) 有且僅有一個特定的稱為 (Root) 的結(jié)點； (2) 其余結(jié)點可分為 m (m0) 個互不相交的有限集 T1, T2, T3, , Tm，其中每一個集合本身又是一棵樹，并稱為根的子樹 (SubTree)。Shanghai Jiao Tong University

17、第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p術(shù)語： T3 T2 T1 結(jié)點的結(jié)點擁有的子樹數(shù)。 度 = 0度 0根結(jié)點以 外的分支 結(jié)點稱為 樹的樹內(nèi)各結(jié)點的度的最大值。 雙親 孩子 兄弟 第 1 層 第 2 層 第 3 層 第 4 層 數(shù)據(jù)元素+ 指向子樹的分支 非空樹中無前驅(qū)結(jié)點的結(jié)點 E F G H I A B C D J K L M 堂兄弟 雙親在同一層的結(jié)點 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p術(shù)語（續(xù)）：結(jié)點的從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。 結(jié)點的以某結(jié)點為根的子樹中的任一結(jié)點。

18、樹的樹中結(jié)點的最大層次。 樹中結(jié)點的各子樹從左至右有次序（最左邊的為第一個孩子）。 樹中結(jié)點的各子樹無次序。 一棵樹可以看成是一個特殊的森林。 把根結(jié)點刪除樹就變成了森林。 給森林中的各子樹加上一個雙親結(jié)點，森林就變成了樹。 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p樹的邏輯結(jié)構(gòu)： 二元組描述方式：Tree = (root, F ) 其中： root為根結(jié)點（含該結(jié)點的數(shù)據(jù)元素） F為該根結(jié)點的子樹集合，若有m棵子樹，則： F = (T1, T2, , Tm) ， Ti = (ri , Fi ) ，Ti 稱做根 roo

19、t 的第 i 棵子樹。顯然：F是包含m棵樹的森林當 m0 時： RF = | i = 1, 2, , m, m 0Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 舉例RF = , , Tree = (A, F ) F = (T1, T2, T3) T1 = (B, F1) T2 = (C, F2) T3 = (D, F3) r1F1= , r2F2= r3F3= , , E F G H I A B C D J K L M Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)

20、p樹的表示方法樹形、文氏圖、凹入圖、廣義表： A 空樹 A B 僅含有根結(jié)點的樹 ABEFK LDHIMJCG E F G H I A B C D J K L M Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p樹的表示方法樹形、文氏圖、凹入圖、廣義表：A B E K L F C G D H M I J E F G H I A B C D J K L M (B(E(K,L),F),C(G),D(H(M),I,J) ) Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)

21、構(gòu)樹結(jié)構(gòu)二叉樹二叉樹p二叉樹定義 n (n0) 個結(jié)點的有限集，或者是空集 (n = 0)，或者由一個根結(jié)點及兩棵互不相交的左子樹和右子樹的二叉樹組成 特性： 每個結(jié)點最多有倆孩子 () 子樹有左右之分，其次序不能顛倒 可以是空集合，根可以有空的左子樹或空的右子樹p對二叉樹的操作算法簡單，且任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣降低樹存儲結(jié)構(gòu)及其運算中的復雜性p注：根據(jù)定義，二叉樹不是樹的一種形態(tài)！因為二叉樹的子樹一定要分左右子樹一定要分左右Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的基本形態(tài)： 空樹；單根結(jié)點；根與

22、左子樹；根與右子樹；根與左右子樹 (a)空二叉樹 (b) 根和空的 左右子樹 (c) 根和左子樹 (d) 根和右子樹 (e) 根和左右子樹 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的基本性質(zhì)： 性質(zhì)1：在二叉樹的第 i 層上至多有 2 i - 1 個結(jié)點 (i 1) （證明略） 性質(zhì)2：深度為 k 的二叉樹至多有 2k1 個結(jié)點（k 1) （證明略） 性質(zhì)3：對任何一棵二叉樹 T，如果其葉子數(shù)為 n0，度為 2 的結(jié)點數(shù)為 n2，則 n0 = n2 + 1 （證明略）2453671p滿二叉樹（ Full bin

23、ary tree ）： 深度為 k 且有 2k- 1 個結(jié)點的二叉樹稱為滿二叉樹 特點：每一層上的結(jié)點數(shù)都達到最大。葉子全部在最底層 編號規(guī)則：從根結(jié)點開始，自上而下，自左而右Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p完全二叉樹 (Complete binary tree) ： 深度為 k 的具有 n 個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為 k 的滿二叉樹中編號為 1 n 的結(jié)點一一 對應(yīng)時，稱之為完全二叉樹 特點：每一層上的結(jié)點數(shù)都達到最大。葉子全部在最底層，編號規(guī)則：從根結(jié)點開始，自上而下，自左而右 葉子只

24、可能分布在層次最大的兩層上 對任一結(jié)點，如果其右子樹的最大層次為 l，則其左子樹的最大層次必為 l 或 l +1245361完全二叉樹 245361非完全二叉樹 滿二叉樹一定是完全二叉樹；完全二叉樹未必滿二叉樹Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p性質(zhì) 4：具有 n 個結(jié)點的完全二叉樹的深度為 log2n + 1p性質(zhì)5：如果對一棵有 n 個結(jié)點的完全二叉樹 (深度為 log2n+1) 的結(jié)點按層序編號 (從第 1 層到第 log2n+1 層，每層從左到右)，則對任一結(jié)點 i (1in)，有： (1) 如果 i =

25、 1，則結(jié)點 i 是二叉樹的根，無雙親；如果 i 1，則其雙親是結(jié)點 i / 2。 (2) 如果 2i n，則結(jié)點 i 為葉子結(jié)點，無左孩子；否則，其 左孩子是結(jié)點 2i。(3) 如果 2i + 1 n，則結(jié)點 i 無右孩子；否則，其右孩子是 結(jié)點 2i + 1。Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的存儲結(jié)構(gòu) 順序存儲 完全二叉樹：用一組地址連續(xù)的存儲單元依次存儲結(jié)點元素，即將編號為 i 的結(jié)點元素存儲在一維數(shù)組中下標為 i 1 的分量中 一般二叉樹：將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組的

26、相應(yīng)分量中 1 2 3 4 5 6 245361完全二叉樹 245361非完全二叉樹 1 2 3 4 5 6 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的存儲結(jié)構(gòu) 鏈表存儲：樹的每個結(jié)點對應(yīng)一個鏈表結(jié)點n 個結(jié)點的二叉鏈表中，有 n + 1 個空指針域 data parentlchildrchildlchild data rchild結(jié)點結(jié)構(gòu) data rchild lchild ABCDEFG A B C D E F G Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法

27、數(shù)據(jù)結(jié)構(gòu)與算法 A B C D E F G 三叉鏈表 ABCDEFGparentdatalchild rchild lchild data parent rchild 結(jié)點結(jié)構(gòu) Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的遍歷 遍歷：順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次 訪問：對結(jié)點作各種處理，如：輸出結(jié)點的信息、修改結(jié)點的數(shù)據(jù)值等，但要求這種訪問不破壞原來的數(shù)據(jù)結(jié)構(gòu) 遍歷目的：得到樹中所有結(jié)點的一個線性排列 遍歷方法： 假設(shè)：L：遍歷左子樹 D：訪問根結(jié)點 R：遍歷右

28、子樹 共有： DLR、LDR、LRD、DRL、RDL、RLD 根結(jié)點 左子樹 右子樹 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的遍歷 遍歷方法若規(guī)定先左后右，則只有前三種情況： 先（根）序遍歷， 中（根）序遍歷， 后（根）序遍歷。 根結(jié)點 左子樹 右子樹 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的遍歷 先序遍歷：若二叉樹為空，則空操作；否則 (1) 訪問根結(jié)點； (2) 先序遍歷左子樹； (3) 先序遍歷右子樹。 先序遍歷的順序

29、為：ABC A B C 先序遍歷的順序為：ABELDHMIJ A B D E LH M I J Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的遍歷 中序遍歷：若二叉樹為空，則空操作；否則 (1)中序遍歷左子樹； (2)訪問根結(jié)點； (3)中序遍歷右子樹。 中序遍歷的順序為：BAC A B C 中序遍歷的順序為：ELBAMHIDJA B D E LH M I J Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p二叉樹的遍歷 后序遍歷：若二叉樹為空，

30、則空操作；否則 (1)后序遍歷左子樹； (2)后序遍歷右子樹； (3)訪問根結(jié)點。 中序遍歷的順序為：BCA A B C 后序遍歷的順序為：LEBMIHJDAA B D E LH M I J Shanghai Jiao Tong University39第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹樹結(jié)構(gòu)結(jié)構(gòu)p二叉樹舉例：C+語言定義二叉樹，以及先序遍歷、深度計算的遞歸算法Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p線索二叉樹 按照某種遍歷方式對二叉樹進行遍歷，可以把二叉樹中所有結(jié)點排序為一個線性序列。在該序列中，除第

31、一個結(jié)點外每個結(jié)點有且僅有一個直接前驅(qū)結(jié)點；除最后一個結(jié)點外每一個結(jié)點有且僅有一個直接后繼結(jié)點。指向直接前驅(qū)結(jié)點和指向直接后續(xù)結(jié)點的指針被稱為線索（Thread），加了線索的二叉樹稱為線索二叉樹 n個結(jié)點二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前趨和后繼結(jié)點的指。 加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded BinaryTree)。 根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)

32、據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p樹的存儲結(jié)構(gòu) 雙親表示法：定義結(jié)構(gòu)數(shù)組，存放樹的結(jié)點，數(shù)據(jù)域數(shù)據(jù)域存放結(jié)點本身信息；雙親域雙親域指示本結(jié)點的雙親結(jié)點在數(shù)組中的位置。 特點：找雙親容易，找孩子難RBACDEFHGKparent 0 R -11 A 02 B 03 C 04 D 1 5 E 16F 37G 68H 69K 6 數(shù)組下標 r = 0 n = 10 data Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p樹的存儲結(jié)構(gòu) 孩子表示法：鏈表存儲。 多重鏈表lchild data rchildlchild data parent

33、 rchild Data child1 child2 childd Data child1 child2 childd parent A B C D E F ABCDEF Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p樹的存儲結(jié)構(gòu) 孩子鏈表法：把每個結(jié)點的孩子結(jié)點排列起來，看成是一個線性表，用單鏈表存儲，則 n 個結(jié)點有 n 個孩子鏈表（葉子的孩子鏈表為空表）。而 n 個頭指針又組成一個線性表，用順序表（含 n 個元素的結(jié)構(gòu)數(shù)組）存儲。特點：找孩子容易， 找雙親難。RBACDEFHGKr=4 n=10 Shanghai Jiao Tong University第二部分第二部分 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法樹結(jié)構(gòu)樹結(jié)構(gòu)p