3.1數(shù)據(jù)結構與算法

1、第三篇 軟件技術基礎3.1 數(shù)據(jù)結構與算法1.1 數(shù)據(jù)結構概述軟件設計的基本過程1、需求分析、總體設計、模塊分割 2、建立數(shù)學模型、解數(shù)學模型的算法 3、程序編制、調(diào)試、結果數(shù)據(jù)結構的研究內(nèi)容1. 非數(shù)值問題的數(shù)學模型2. 實現(xiàn)該數(shù)學模型的具體算法。數(shù)據(jù)結構的研究對象(1)、如何對被加工對象進行邏輯組織(2)、如何把加工對象存儲到計算機中(3)、對被加工對象進行數(shù)據(jù)處理基本概念和術語1. 基本術語 （1）數(shù)據(jù)：描述客觀事物的數(shù)字、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。數(shù)字、字符、聲音、圖形、圖像等 （2）數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中常常作為一個整體進行考慮和處

2、理，如紀錄/結構。 （3）數(shù)據(jù)項：數(shù)據(jù)的不可分割的最小單位，如結構體中的域/成員。 （4）數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。2. 數(shù)據(jù)結構：相互之間存在特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)之間存在著某種特定的關系，數(shù)據(jù)元素之間的關系，稱為“結構” 數(shù)據(jù)結構=關系+實體定義： 按照一定邏輯關系組織起來的、存儲在計算機中的一批數(shù)據(jù), 以及在這些數(shù)據(jù)上定義了一個運算的集合。 形式定義： 數(shù)據(jù)結構為一個二元組 (D,S) 其中：D是數(shù)據(jù)元素的有限集，S是D上關系的有限集（2）四種基本結構（邏輯結構） 集合：元素僅屬于同一個集體，沒有其他關系。 線性結構：存在一對一關系，順序關系。 樹型結

3、構：存在一對多關系，層次關系。 圖狀結構：存在多對多關系， 又稱網(wǎng)狀結構。（3）物理結構：數(shù)據(jù)結構在計算機中的表示，又稱存儲結構。 主要存儲結構： 順序存儲、鏈接存儲抽象數(shù)據(jù)類型定義：是指一個數(shù)據(jù)模型以及定義在該數(shù)據(jù)模型上的一組操作。抽象的與具體的相對應示例： int a,b; 則a和b可以進行+、-、*、/的運算2和6則是具體的int數(shù)據(jù)對數(shù)據(jù)的操作與數(shù)據(jù)結構密切相關的是定義在數(shù)據(jù)結構之上的一組操作。操作的種類是沒有限制的，如算術運算等?？筛鶕?jù)需要定義，基本操作主要有如下幾種： 1) 插入 2) 刪除 3) 更新 4) 查找 5) 排序算法和算法分析1、算法的重要特性:(1)可行性 （用于描

4、述算法的操作都是行得通的）(2)有窮性 ：能執(zhí)行結束(3)確定性 ：對于相同的輸入只能得到相同的輸出 (4) 0至多個輸入(5) 1至多個輸出算法與數(shù)據(jù)結構的關系計算機科學家沃斯（N.Wirth）提出的:“算法+數(shù)據(jù)結構=程序” 對實際問題選擇一種好的數(shù)據(jù)結構，加上一個好的算法，而好的算法很大程度上取決于描述實際問題的數(shù)據(jù)結構。算法與數(shù)據(jù)結構是互相依賴、互相聯(lián)系的。算法總是建立在一定數(shù)據(jù)結構之上的；算法不確定，就無法決定如何構造數(shù)據(jù)。3. 算法設計的要求（1）正確性 算法應當滿足問題的需要。（2）可讀性 首先是人的閱讀和理解，然后才是機器執(zhí)行（3）健壯性 / 容錯性 當輸入非法數(shù)據(jù)時，算法也能

5、進行適當處理，不會產(chǎn)生莫名其妙的結果。（4）效率與低存儲量需求 算法的執(zhí)行時間和存儲空間要求算法分析 算法性能的評價 評價標準： 1）實現(xiàn)算法所需的計算時間 2）實現(xiàn)算法所需的存儲空間 3）算法的簡單性 度量算法執(zhí)行時間的兩種方法 1）事后統(tǒng)計法， 此方法有兩個缺陷： a. 必須先運行程序；b. 運行時間依賴于計算機軟硬件環(huán)境 2）事前分析估算法 此方法取決于多個因素：程序執(zhí)行所需時間取決于多個因素：1) 算法選用的策略。2）問題的規(guī)模。3）書寫程序的語言。4）編譯程序所產(chǎn)生的機器代碼的質(zhì)量。5）機器執(zhí)行指令的速度。 不考慮計算機軟硬件環(huán)境，特定算法的運行工作量大小只與問題的規(guī)模n有關。5 .

6、 時間復雜度定義： 一般情況下，算法中基本操作執(zhí)行的時間是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作 T(n) = O(f(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。 例: T(n)=O(n); /如：查找 T(n)=O(n3) /如：矩陣相乘 語句頻度：語句重復執(zhí)行的次數(shù)。6. 空間復雜度算法所需存儲空間的度量（1）存儲算法本身所占用的空間（2）算法的輸入/輸出數(shù)據(jù)占用的空間（3）算法在運行過程中臨時占用的輔助空間原地工作：若輔助空間相對于輸入數(shù)據(jù)量是常數(shù)，則稱此算法是原地工作。若所占空間量依賴于特定的輸入，按

7、最壞情況來分析。3.2 線性表線性表的基本概念線性表由一組具有相同屬性的數(shù)據(jù)元素構成。 1 . 線性表的定義 線性表L是n（n0）個具有相同屬性的數(shù)據(jù)元素a1，a2，a3，an組成的有限序列，其中：n稱為線性表的長度。 當n=0時稱為空表，即不含有任何元素。 非空線性表(n0)記作： (a1，a2，an) 數(shù)據(jù)元素 ai(1in)只是一個抽象的符號，其具體含義視具體情況而定。例1、26個英文字母組成的字母表 （A，B，C、Z） 例2、一組數(shù)字 （6，17，28，50，92，188）例3、線性表的邏輯特征1) 非空的線性表，有且僅有一個開始結點a1，它沒有直接前趨，而僅有一個直接后繼a2；2)

8、有且僅有一個終端結點an，它沒有直接后繼，而僅有一個直接前趨a n-1；3) 其余的內(nèi)部結點ai(2in-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。線性表是一種典型的線性結構。 數(shù)據(jù)的運算是定義在邏輯結構上的，而運算的具體實現(xiàn)則是在存儲結構上進行的。2. 線性表的抽象數(shù)據(jù)類型ADT Linear_list 數(shù)據(jù)對象：D=ai | aiElemSet , i=1,2,n, n0； 數(shù)據(jù)關系：R= | ai-1 ,aiD, i=2,3, ,n 基本操作：初始化空線性表； 求線性表表長； 取線性表的第i個元素； 在線性表的第i個位置插入元素x； 刪除線性表的第i個元素； 修改線性表中

9、的第i個元素； 按某種要求重排線性表中各元素的順序； 按某個特定值查找線性表中的元素； ADT Linear_list；2.2 線性表的存儲和運算線性表有兩種基本的存儲結構： 順序存儲結構和鏈式存儲結構。1.線性表的順序存儲結構(順序表)順序表具有以下兩個基本特點： 1)線性表的所有元素是連續(xù)存放的。 2)線性表中數(shù)據(jù)元素的存儲順序和邏輯順序相同 線性表的數(shù)據(jù)元素的類型相同，每個元素所占用的空間相同。 使用數(shù)組來存儲.在順序存儲結構中查找元素很方便 一般用數(shù)組實現(xiàn)對線性表的連續(xù)存儲。設最多存儲Maxsize個元素，在C語言中可用數(shù)組elemMaxsize來存儲數(shù)據(jù)元素，整型變量length保存

10、線性表的長度。線性表的第l，2，n個元素分別存放在此數(shù)組下標為0，1，length-1數(shù)組元素中i-1. 線性表的建立線性表的順序存儲結構至少需要兩個分量：數(shù)組elemMaxsize和表長度lengthC+中，數(shù)組和線性表長度可以作為類的數(shù)據(jù)成員(私有成員)，對線性表的各種操作可作為類的成員函數(shù)成員函數(shù)多是公有函數(shù)，提供類的對外接口。在C+中，可用下述類定義來描述順序表：typedef int ElemType; /數(shù)據(jù)元素的類型const int MAXSIZE=100; /數(shù)組的容量class SqList private: ElemType elemMAXSIZE;/數(shù)組 int len

11、gth; /線性表長 public: SqList( void); /構造函數(shù) SqList() ; /析構函數(shù) void Creat() ; /創(chuàng)建一個線性表 void PrintOut(); /輸出線性表 void Insert( int i, ElemType e); /插入函數(shù) ElemType Delete(int i); /刪除函數(shù) ; /類定義結束 順序存儲結構運算實現(xiàn)1初始化線性表(構造一個空表) 用構造函數(shù)構造一個空表，表長度為0，即為建立空表 SqList:SqList() length=0; /構造函數(shù)，構造空表2建立一個長度為length的新表 void SqList:

12、Creat() /建立一個簡表函數(shù) coutlength; coutn Input Data:n ; for(int k=0; kelemk; 3. 輸出線性表函數(shù) void SqList:PrintOut() coutn length=length ; coutn PrintOut Data:n ; for(int k=0; klength; k+) coutsetw(6)elemk; coutendl; 4線性表的插入在長度為length的順序表的第i個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)元素x，需將第i個元素及其后元素依次向后移動一個位置，空出第i個位置，然后把x插入到第i個存儲位置，順序表的長

13、度增加1。 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum插入xvoid SqList:Insert( int i, ElemType e) int j; i-; /邏輯位置換算為C+數(shù)組下標值 if(ilength) cout “ i Error!”i; j-) elemj=elemj-1; /移動元素 elemi=e; /插入元素 ength+; /線性表長加1 5順序表的刪除運算 刪除運算將表中第 i 個元素從線性表中去掉，

14、原表長為 n 的線性表(a1，a2， ，ai-1，ai，ai+1，an) ，刪除后線性表長變?yōu)?n-1的表 (a1，a2， ，ai-1，ai+1， ，an) 。 如下圖所示。 0 a0 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numanum 線性表的刪除運算通過以下兩個操作來實現(xiàn)： (1) 線性表中第i+1個至第n個元素（共n-i個元素）依次向前移動一個位置。 (2)線性表長度減1。 ElemType SqList:Delete( int i ) ElemType x; i

15、nt j; i-; /轉換成C+數(shù)組下標 if(ilength-1) cout i Error!endl; x=-1; /判斷刪除位置 else x=elemi; for(j=i; jnext=s(2)(3)ps-next=p-nexta(1)b單鏈表插入算法void LinkList:Insert(int i, ElemType x) NodeType *p,*q,*s; int k=1; /計數(shù)器k，用于尋找i位置 q=Head; p=Head -next; while(knext; k+; if(k=i) s=new NodeType; s-data=x; s-next=p ; q-ne

16、xt=s; coutn 插入成功。 endl; else coutn i不存在。next; /p指向第一個數(shù)據(jù)結點 while(knext; k+; if(p!=NULL) x=p-data; q-next=p-next; delete p; coutn 刪除結點成功。endl; else coutn i不存在。endl; x=-1; return x; 3. 循環(huán)鏈表1）循環(huán)鏈表是一種首尾相接的鏈表。 循環(huán)鏈表最后一個結點的next指針不為 0 (NULL)， 而是指向表頭結點。在循環(huán)鏈表中沒有NULL 特點：循環(huán)鏈表中，從任一結點出發(fā)都可訪問到表中 所有結點；而在單鏈表中，必須從頭指針開始

17、， 否則無法訪問到該結點之前的其他結點。循環(huán)鏈表與單鏈表不同的是鏈表中表尾結點的 指針域不是NULL，而是鏈表頭結點的指針Head循環(huán)鏈表的示例帶表頭結點的循環(huán)鏈表4.雙向鏈表 (Doubly Linked List)雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。1) 雙向鏈表的結點結構： 前驅(qū)方向 (a)結點結構 后繼方向雙向鏈表通常采用帶表頭結點的循環(huán)鏈表形式。非空雙向循環(huán)鏈表 空表2）雙向循環(huán)鏈表存儲結構的描述 typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; D

18、uLNode, *DuLinkList;DuLinkList d,p;棧和隊列 受限制的線性表棧的定義及其實現(xiàn) 棧(Stack)是只能在表的一端進行插入或刪除操作的線性表。通常把允許插入和刪除操作的一端稱為棧頂(Top)，而另一端稱為棧底(Bottom)。表為空時稱為空棧。棧的主要運算是入棧和出棧。 如果按a1，a2，an的順序進棧，則出棧順序為an，an-1，a1。因此，棧又稱為“后進先出”（Last In First Out）的線性表，簡稱LIFO表。 棧也有順序棧和鏈棧兩種存儲結構。順序棧易產(chǎn)生“上溢”現(xiàn)象，而鏈棧不容易產(chǎn)生。注意對棧的操作只能在棧頂進行。 棧示意圖棧的抽象數(shù)據(jù)類型ADT

19、 Stack 數(shù)據(jù)對象：D=ai |aiElemSet , i=1,2,n,n0 ; 數(shù)據(jù)關系：R= | ai-1 ,aiD, i=2,3,n 約定an 端為棧頂，a1 端為棧底。 基本操作：初始化一個空棧； 判棧空，空棧返回True,否則返回False； 進棧，在棧頂插入一個元素； 出棧，在棧頂刪除一個元素； 取棧頂元素值； 置棧為空狀態(tài)； 求棧中數(shù)據(jù)元素的個數(shù)； 銷毀棧； ADT Stack； 32棧的表示和操作的實現(xiàn)1、順序存儲的棧 限定在表尾進行插入和刪除操作的順序表棧頂指針top=1棧底，空棧時棧頂指針top=0；進棧時，棧頂指針top加，當top達到數(shù)組的最大下標值時為棧滿；出棧時

20、，棧頂指針top減。順序棧類定義typedef int ElemType; /數(shù)據(jù)元素的類型const int MAXSIZE=100; /數(shù)組的容量class SqStack private: ElemType elemMAXSIZE; int top; public: SqStack () top=0； /構造函數(shù), 初始化一個空棧 SqStack(); /析構函數(shù) void SetEmpty() top=0； /置已有的棧為空棧 int IsEmpty() ; /判斷棧是否為空 void Push( ElemType e); /進棧 ElemType Pop(); /出棧 void Pr

21、intOut(); /輸出棧中數(shù)據(jù)元素 ElemType GetPop(); /取棧頂元素數(shù)據(jù) ;輸出棧中所有數(shù)據(jù)元素void SqStack:PrintOut() /輸出函數(shù),不改變top coutn PrintOut Data:n ; if(top=0)cout=1;k-) coutsetw(6)elemk; coutendl; 判斷棧是否為空int SqStack:IsEmpty() /判斷棧是否為空 if(top=0) return 1; else return 0; 進棧操作 在棧頂插入數(shù)據(jù)元素e。在進棧時，先使棧頂指針top自加1，然后使數(shù)據(jù)元素e進棧。算法實現(xiàn)如下：void Sq

22、Stack:Push( ElemType e) if(top=MAXSIZE-1) coutn棧滿溢出endl; /判斷棧是否為滿 else top+; elemtop=e; /數(shù)據(jù)元素e進棧 出棧操作 刪除棧頂數(shù)據(jù)元素。出棧時先把棧頂元素值保存，然后棧頂指針top自減，返回刪除的數(shù)據(jù)元素值。 ElemType SqStack:Pop( ) ElemType x; if(top=0) cout n 棧為空！endl; x=0; /表示未曾出棧 else x=elemtop; /出棧 top-; return x; 棧的鏈式存儲結構用單鏈表存儲棧的結點數(shù)據(jù)元素結點定義typedef int El

23、emType;typedef struct Node ElemType data; /數(shù)據(jù)域 struct Node *next; /地址域 StackNode;棧的操作限定在棧頂進行進棧-在鏈表首結點前插入數(shù)據(jù)出棧-刪除鏈表首結點算法與鏈表的插入與刪除相同隊列定義和操作 隊列（Queue）是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。通常把允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊頭（front）。隊列中元素如果按a1，a2，an的順序進隊，則出隊的順序仍為a1，a2，an。因此，隊列又稱為“先進先出”（First In First Out）的線性表，簡稱FIFO

24、表 。 隊列也有順序隊列和鏈隊列兩種存儲結構。在順序隊列中，為避免“假滿”現(xiàn)象，一般采用循環(huán)隊列（即首尾相接）。隊的示意圖ADT Queue 數(shù)據(jù)對象：D=ai | aiElemSet , i=1,2,n, n0 ; 數(shù)據(jù)關系：R= |ai-1,aiD, i=2,3,n /約定a1端為隊頭，an端為隊尾。 基本操作：初始化一個空隊列； 判隊空，空隊返回True,否則返回False； 入隊，在隊尾插入一個元素； 出隊，在隊頭刪除一個元素； 取隊頭數(shù)據(jù)元素值； 置隊列為空狀態(tài)； 銷毀隊列； ADT Queue;隊列的抽象數(shù)據(jù)類型隊列順序存儲結構 隊列的順序存儲用一維數(shù)組來存儲隊列中的元素。為了指示

25、對頭和隊尾的位置，需要設置隊頭front和隊尾rear兩個指針，并約定：頭指針front指向隊列頭元素的前一位置，尾指針rear指向隊尾元素。 隊列順序存儲結構 隊列順序存儲結構 存在問題：“假溢出”解決方法： 采用平移元素方法 采用循環(huán)隊列解決隊列順序存儲結構-循環(huán)隊列 隊列順序存儲結構-循環(huán)隊列循環(huán)隊列判斷隊空條件是：rear=front循環(huán)隊列判斷隊滿條件是：(rear+1)%MAXSIZE=front進隊操作如下：rear=(rear+1)% MAXSIZE; elemrear=x; 出隊操作的如下：front=(front+1)% MAXSIZE; x=elemfront; 循環(huán)隊列

26、類定義class SeQueue private: ElemType elemMAXSIZE; int front,rear; public: SeQueue() front=0; rear=0; /初始化空隊列 SeQueue() ; int Empty(); void Display(); /輸出隊列 void AddQ(ElemType x); /進隊 ElemType DelQ(); /出隊 ElemType GetFront(); ; /循環(huán)隊列類定義結束循環(huán)隊列類定義判斷隊列是否為空int SeQueue:Empty() if(rear=front) return 1; else

27、return 0; 取隊頭元素ElemType SeQueue:GetFront() /取隊首元素，不出隊 ElemType x; if(front= rear) /判斷隊列是否為空 coutn Queu is Empty! endl; x=-1; else x= elem(front+1)%MAXSIZE; return x; 循環(huán)隊列的進隊算法 void SeQueue:AddQ(ElemType x) if(rear+1) % MAXSIZE=front) /判斷是否滿隊 coutn Queu is Full! endl; else rear=(rear+1) % MAXSIZE; /尾

28、指針加1 elemrear=x; /x進隊列 循環(huán)隊列的出隊算法 ElemType SeQueue:DelQ () if(front=rear) /判斷隊列是否為空 coutn Queue is Empty! 0，則: 有一個特定的稱之為根(root)的結點，它只有后繼，但沒有前驅(qū)； 除根以外的其它結點劃分為m (m 0)個互不相交的有限集合T0, T1, , Tm-1，每個集合本身又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。2. 樹的基本術語結點擁有的子樹數(shù)稱為結點的度。度為0的結點稱為葉子或終端結點。度不為0的結點稱為非終

29、端結點或分支結點。結點的層次 樹中根結點的層次為1，根結點子樹為第2層，以此類推。樹的度 樹中所有結點度的最大值。樹的深度 樹中所有結點層次的最大值。有序樹、無序樹 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。二叉樹 (Binary Tree)二叉樹的定義二叉樹的五種不同形態(tài) 一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。特點：1）每個結點的度2；2）是有序樹基本操作：二叉樹的建立和遍歷二叉樹的抽象數(shù)據(jù)類型 二叉樹是一種重要的樹型結構，但二叉樹不是樹的特例。 二叉樹的 5 種形

30、態(tài)分別為：空二叉樹，只有根結點的二叉樹，根結點和左子樹，根結點和右子樹，根結點和左右子樹。 二叉樹與樹的區(qū)別：二叉樹中每個結點的孩子至多不超過兩個，而樹對結點的孩子數(shù)無限制；另外，二叉樹中結點的子樹有左右之分，而樹的子樹沒有次序。 性質(zhì)1 若二叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i-1個結點。(i 1)性質(zhì)2 深度為k的二叉樹最多有 2k-1個結點。(k 1)二叉樹的性質(zhì)定義1 滿二叉樹(Full Binary Tree) 一棵深度為k且有2k -1個結點的二叉樹稱為滿二叉樹。 定義2 完全二叉樹(Complete Binary Tree) 若設二叉樹的深度為h，則共有h層。

31、除第h層外，其它各層(0h-1)的結點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結點。完全二叉樹的特點是：只允許最后一層有空缺結點且空缺在右邊，即葉子結點只能在層次最大的兩層上出現(xiàn)；性質(zhì)3 具有n個結點的完全二叉樹的深度為 log2n +1 二叉樹的存儲結構1. 順序存儲結構（數(shù)組表示） 順序存儲二叉樹的具體方法是：在一棵具有n個結點的完全二叉樹中，從根結點開始編號為1，自上到下，每層自左至右地給所有結點編號，這樣可以得到一個反映整個二叉樹結構的線性序列；然后將完全二叉樹上編號為i的結點依次存儲在一維數(shù)組al . n中下標為i的元素中。 完全二叉樹的數(shù)組表示 一般二叉樹的數(shù)組表示 由于一般二叉

32、樹必須仿照完全二叉樹那樣存儲，可能會浪費很多存儲空間，單支樹就是一個極端情況。單支樹2.鏈式存儲結構鏈式存儲是使用鏈表存儲二叉樹中的數(shù)據(jù)元素，鏈表的一個結點相應地存儲二叉樹的一個結點。常見的二叉樹的鏈式存儲結構有兩種：二叉鏈表和三叉鏈表。二叉鏈表是指鏈表中的每個結點包含兩個指針域和一個數(shù)據(jù)域，分別用來存儲指向二叉樹中結點的左右孩子的指針及結點信息。三叉鏈表是指鏈表中的每個結點包含三個指針域和一個數(shù)據(jù)域，相比二叉鏈表多出的一個指針域則用來指向該結點的雙親結點。 兩種鏈表，頭指針都指向二叉樹的根結點。typedef struct BiTNode /二叉鏈表的定義TElemType data;Str

33、uct BiTNode *lchild,*rchild;BiTNode, *BiTree;二叉樹鏈表表示的示例遍歷二叉樹(Traversing Binary Tree) 所謂樹的遍歷，就是按某種次序訪問樹中的結點，要求每個結點訪問一次且僅訪問一次。 遍歷的結果：產(chǎn)生一個關于結點的線性序列。 設訪問根結點記作 D 遍歷根的左子樹記作 L 遍歷根的右子樹記作 R 則可能的遍歷次序有 先序 DLR DRL 逆先序 中序 LDR RDL 逆中序 后序 LRD RLD 逆后序先序遍歷 (Preorder Traversal)先序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則訪問根結點 (D)；先序遍

34、歷左子樹 (L)；先序遍歷右子樹 (R)。右圖遍歷結果 -+a*b-cd/ef先序遍歷二叉樹的遞歸算法void PreOrderTraverse(BiTree T)if (T)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹 (L)；訪問根結點 (D)；中序遍歷右子樹 (R)。遍歷結果 a + b * c - d - e / f中序遍歷 (Inorder Traversal)中序遍歷二叉樹的遞歸算法void InOrderTrav

35、erse(BiTree T)if (T) InOrderTraverse(T-lchild);printf(%c,T-data);InOrderTraverse(T-rchild);后序遍歷 (Postorder Traversal)后序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則后序遍歷左子樹 (L)；后序遍歷右子樹 (R)；訪問根結點 (D)。右圖遍歷結果 abcd-*+ef/-后序遍歷二叉樹的遞歸算法void PostOrderTraverse(BiTree T)if (T) PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchil

36、d);printf(%c,T-data);二叉樹的顯示輸出void PrintBiTree(BiTree T,int n)int i; char ch= ;if (T) PrintBiTree(T-rchild,n+1);for (i=1;idata);PrintBiTree(T-lchild,n+1);樹的存儲結構樹和森林多重鏈表（標準存儲結構）定長結構 （n為樹的度）指針利用率不高不定長結構 d為結點的度，節(jié)省空間，但算法復雜一般采用定長結構如有n個結點，樹的度為k，則共有n*k個指針域，只有n-1個指針域被利用，而未利用的指針域為：n*k-(n-1) =n(k-1)+1，未利用率為：( n(k-1)+1)/nk n(k-1)/nk=(k-1)/k樹的度越高，未利用率越高。 data data child1child2child3childndchild2child3childd3.4 排序與查找插入排序 （直接插入、折半插入、表插入排序、希爾排序）交換排序 （起泡排序、快速排序）選擇排序 （簡單選擇排序、樹形選擇排序、堆排序）排序 插入排序 (Insert Sorting)直接插入排序的基本思想是：當插入第i (i 1) 個對象時，前面的V0, V1, , vi-1已經(jīng)排好序。這時，用vi的關鍵字與vi-1, vi-2, 的關鍵字順序進行比較，找到