《零售業(yè)現(xiàn)場(chǎng)管理》

第4單元非線(xiàn)性結(jié)構(gòu)(一）第二章2.1～2.4節(jié)樹(shù)的基本概念和邏輯結(jié)構(gòu)二叉樹(shù)的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷操作及有關(guān)算法特殊二叉樹(shù)的表示及性質(zhì)樹(shù)、森林、二叉樹(shù)的轉(zhuǎn)換1第4單元非線(xiàn)性結(jié)構(gòu)(一）12.1樹(shù)的邏輯結(jié)構(gòu)及其運(yùn)算一.樹(shù)的定義1.邏輯定義數(shù)據(jù)結(jié)構(gòu)：Tree=（D，R）其中：D具有相同數(shù)據(jù)類(lèi)型的元素的集合；關(guān)系R滿(mǎn)足：1)存在唯一的元素沒(méi)有前趨,稱(chēng)為根；2)其余元素都有且只有一個(gè)前趨；3)所有元素，或有若干個(gè)互不相同的后繼，或無(wú)后繼；則稱(chēng)Tree為樹(shù)。22.1樹(shù)的邏輯結(jié)構(gòu)及其運(yùn)算一.樹(shù)的定義22.樹(shù)的遞歸定義樹(shù)是一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T，有一個(gè)特定結(jié)點(diǎn)稱(chēng)為根，其余結(jié)點(diǎn)分為m（m0）個(gè)互不相交的集合T1，T2，…,Tm。每個(gè)集合又是一棵樹(shù)，被稱(chēng)為這個(gè)根的子樹(shù)。32.樹(shù)的遞歸定義33.樹(shù)結(jié)構(gòu)舉例書(shū)目錄目錄樹(shù)樹(shù)結(jié)構(gòu)C1（章）BOOK

S1.1(節(jié))S1.2C1C2C3

C2S2.1S1.1S1.2S2.1S2.2S2.3S2.11S2.12S2.2S2.1.1S2.1.2

S2.3C343.樹(shù)結(jié)構(gòu)舉例書(shū)目錄目錄樹(shù)4.樹(shù)的一般表示形式

ABCDEFKLGHIJMA(a)(b)(a)只有根結(jié)點(diǎn)的樹(shù)(b)一般的樹(shù)54.樹(shù)的一般表示形式ABCDEFKLGHIJMA(a)(b二.基本術(shù)語(yǔ)（一）結(jié)點(diǎn)的度結(jié)點(diǎn)擁有的子樹(shù)數(shù)；A的度為3。根結(jié)點(diǎn)無(wú)前趨的結(jié)點(diǎn)；例如，A結(jié)點(diǎn)。支結(jié)點(diǎn)度不為0的結(jié)點(diǎn)；如B，C，D等。葉結(jié)點(diǎn)無(wú)后繼的結(jié)點(diǎn)；如K，L，M。子結(jié)點(diǎn)和父結(jié)點(diǎn)兄弟結(jié)點(diǎn)擁有同一父結(jié)點(diǎn)的結(jié)點(diǎn)之間互為兄弟結(jié)點(diǎn)結(jié)點(diǎn)的層次根結(jié)點(diǎn)層次為1,其它結(jié)點(diǎn)遞增6二.基本術(shù)語(yǔ)（一）結(jié)點(diǎn)的度結(jié)點(diǎn)擁有的子樹(shù)數(shù)；A的度為3二.基本術(shù)語(yǔ)（二）樹(shù)的度樹(shù)中結(jié)點(diǎn)的最大度數(shù)；上述樹(shù)的度為3。有序樹(shù)結(jié)點(diǎn)的各子樹(shù)看成從左至右有順序且不能互換，則該樹(shù)為有序樹(shù)。否則為無(wú)序樹(shù)。路徑由結(jié)點(diǎn)序列組成.長(zhǎng)度長(zhǎng)度等于路徑中結(jié)點(diǎn)數(shù)-1.高度從一結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑為該結(jié)點(diǎn)的高度；例如，結(jié)點(diǎn)A到M的高度為4。深度從根結(jié)點(diǎn)到某結(jié)點(diǎn)的路徑為該結(jié)點(diǎn)的深度；M的深度為4。森林0棵或多棵互不相交的樹(shù)的集合。7二.基本術(shù)語(yǔ)（二）樹(shù)的度樹(shù)中結(jié)點(diǎn)的最大度數(shù)；上述樹(shù)的度為3三.樹(shù)的操作1.setnull(T)將T置為空樹(shù)2.ROOT(x)求x所在樹(shù)的根結(jié)點(diǎn)3.PARENT(T,x）樹(shù)T中x結(jié)點(diǎn)的雙親；4.CHILD(T,x,i）求T中結(jié)點(diǎn)x的第i個(gè)子結(jié)點(diǎn)。5.ins_child(T,y,i,x)x作為T(mén)中y結(jié)點(diǎn)的第i個(gè)孩子6.del_child(T,x,i)刪除結(jié)點(diǎn)x的第i個(gè)子樹(shù)。7.TRAVERSE(T）遍歷樹(shù)T。按次序依次訪問(wèn)樹(shù)中各個(gè)結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。8三.樹(shù)的操作1.setnull(T)將T置為空樹(shù)82.2二叉樹(shù)一.二叉樹(shù)定義及運(yùn)算1.定義

n個(gè)結(jié)點(diǎn)的集合（n0）T=所有子樹(shù)都有左、右之分

92.2二叉樹(shù)一.二叉樹(shù)定義及運(yùn)算92.二叉樹(shù)的五種基本形態(tài)

（a）（b）（c）（d）（e）O空結(jié)點(diǎn)

O單個(gè)結(jié)點(diǎn)OO右子樹(shù)為空的二叉樹(shù)OO左子樹(shù)為空的二叉樹(shù)OOO左、右子樹(shù)非空的二叉樹(shù)102.二叉樹(shù)的五種基本形態(tài)（a）（d）O空結(jié)點(diǎn)3.二叉樹(shù)與樹(shù)的區(qū)別表達(dá)形式（對(duì)3個(gè)結(jié)點(diǎn)）樹(shù)二叉樹(shù)（a）（b）（c）（d）（e）有兩種不同形式OOO（a）OOOOOOOOOOOOOOO有五種不同形式OOO（b）113.二叉樹(shù)與樹(shù)的區(qū)別表達(dá)形式（對(duì)3個(gè)結(jié)點(diǎn)）有兩種不同形式O二叉樹(shù)與樹(shù)的區(qū)別（二）二叉樹(shù)是一種特定的樹(shù)結(jié)構(gòu)，但不是普通樹(shù)的特殊情況；二叉樹(shù)可以為空；而樹(shù)不能為空；非空二叉樹(shù)是有序樹(shù),而樹(shù)可以是有序或無(wú)序樹(shù)。12二叉樹(shù)與樹(shù)的區(qū)別（二）124.二叉樹(shù)的性質(zhì)性質(zhì)一二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i

1)性質(zhì)二深度為k的二叉樹(shù)上最多含有2k-1個(gè)結(jié)點(diǎn)（k

1）。134.二叉樹(shù)的性質(zhì)性質(zhì)一13

123865741091112131415第3層有23-1個(gè)結(jié)點(diǎn).深度為4,則最多有24-1個(gè)結(jié)點(diǎn).14123865741091112131415第3層有23-15.二叉樹(shù)的基本運(yùn)算1.setnull(BT)將二叉樹(shù)BT置空2.root(x)x所在二叉樹(shù)的根3.parent(BT,x）x結(jié)點(diǎn)的雙親4.lchild(BT,x）求x左孩子結(jié)點(diǎn)rchild(BT,x)求x右孩子結(jié)點(diǎn)5.ins_lchild(BT,x,y)y置為x的左孩子ins_rchild(BT,x,y)y置為x的右孩子6.del_lchild(BT,x)刪除x的左子樹(shù)del_rchild(BT,x)刪除x的右子樹(shù)7.TRAVERSE(BT）遍歷樹(shù)T155.二叉樹(shù)的基本運(yùn)算1.setnull(BT)二.二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)

dataleftprightp左指針數(shù)據(jù)右指針ABCDEFGABDCEFGNULL特點(diǎn):找子易,找父難.1.二叉鏈表NULLNULL16二.二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)dataleftprightp二.二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)(續(xù))

parentdatarightp左指針數(shù)據(jù)父結(jié)點(diǎn)右指針ABCDEFGC特點(diǎn):找子、找父都易leftpABDEGF2.三叉鏈表17二.二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)(續(xù))parentdatarig三.特殊二叉樹(shù)---滿(mǎn)二叉樹(shù)1.滿(mǎn)二叉樹(shù)若深度為k的二叉樹(shù)T中共有2k-1個(gè)結(jié)點(diǎn)(k≥1),則稱(chēng)T為滿(mǎn)二叉樹(shù)。

（a）滿(mǎn)二叉樹(shù)（b）非滿(mǎn)二叉樹(shù)OOOOOOOOOOOOO18三.特殊二叉樹(shù)---滿(mǎn)二叉樹(shù)1.滿(mǎn)二叉樹(shù)OOOOOOOO三.特殊二叉樹(shù)---滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)的性質(zhì)對(duì)滿(mǎn)二叉樹(shù)從第1層開(kāi)始,自上而下、從左至右對(duì)每個(gè)結(jié)點(diǎn)由1開(kāi)始編號(hào)，則深度為k的滿(mǎn)二叉樹(shù)結(jié)點(diǎn)編號(hào)i(1≤i≤2k-1-1),滿(mǎn)足以下關(guān)系：1)i的左子樹(shù)根編號(hào)為2*i，右子樹(shù)根編號(hào)為2*i+12)i的父結(jié)點(diǎn)編號(hào)為int(i/2)應(yīng)用:用一維數(shù)組存儲(chǔ)滿(mǎn)二叉數(shù)的結(jié)點(diǎn),由一個(gè)結(jié)點(diǎn)的編號(hào)，計(jì)算出左、右子樹(shù)的根及父結(jié)點(diǎn)的編號(hào)19三.特殊二叉樹(shù)---滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)的性質(zhì)19滿(mǎn)二叉樹(shù)存儲(chǔ)舉例

1432576

12345671234567第i個(gè)結(jié)點(diǎn)存放在第i個(gè)位置；第i個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)在第i/2個(gè)位置;第i個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)就存放在第2*i的個(gè)位置;右子存放在第2*i+1位置.20滿(mǎn)二叉樹(shù)存儲(chǔ)舉例143257612三.特殊二叉樹(shù)---完全二叉樹(shù)深度為k的二叉樹(shù)T,每層結(jié)點(diǎn)數(shù)目若滿(mǎn)足:第i層(1≤i≤k-1)的結(jié)點(diǎn)個(gè)數(shù)均為2i-1第k層從右邊連續(xù)缺若干個(gè)結(jié)點(diǎn)這樣的樹(shù)稱(chēng)為完全二叉樹(shù)。特點(diǎn):葉結(jié)點(diǎn)只能出現(xiàn)在層次最大的兩層上.

（a）完全二叉樹(shù)（b）非完全二叉樹(shù)OOOOOOOOOOO21三.特殊二叉樹(shù)---完全二叉樹(shù)深度為k的二叉樹(shù)T,每層結(jié)點(diǎn)數(shù)完全二叉樹(shù)的性質(zhì)設(shè)完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為n，深度為k，某結(jié)點(diǎn)編號(hào)為i(1≤i≤k-1),則有：1)若i>1,則i的雙親結(jié)點(diǎn)編號(hào)為int(i/2)2)若2*i≤n,則i的左子結(jié)點(diǎn)的編號(hào)為2*i,否則i為葉結(jié)點(diǎn);3)若2*i+1≤n,則i的右子結(jié)點(diǎn)的編號(hào)為2*i+1,否則,i為葉結(jié)點(diǎn).完全二叉樹(shù)也可以采用一維樹(shù)組作為存儲(chǔ)結(jié)構(gòu),且方法完全同滿(mǎn)二叉樹(shù).22完全二叉樹(shù)的性質(zhì)設(shè)完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為n，深度為k，某結(jié)點(diǎn)三.特殊二叉樹(shù)---平衡二叉樹(shù)1.平衡因子:二叉樹(shù)上任一結(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)深度的差值。2.平衡二叉樹(shù):二叉樹(shù)中,每個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值都不大于1。（a）平衡二叉樹(shù)（b）非平衡二叉樹(shù)OOOOOOOOOOOOOOOO23三.特殊二叉樹(shù)---平衡二叉樹(shù)1.平衡因子:二叉樹(shù)上任一結(jié)三.特殊二叉樹(shù)---二叉排序樹(shù)定義:或者是空二叉樹(shù)；或者是：左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；右子樹(shù)上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值；左、右子樹(shù)本身又是一棵二叉排序樹(shù)。24三.特殊二叉樹(shù)---二叉排序樹(shù)定義:24二叉排序樹(shù)例題例(P65)有7個(gè)元素的序列:10,18,3,3,9,13,25試根據(jù)算法的基本思想構(gòu)造一棵二叉排序樹(shù)a）二叉排序樹(shù)b）非二叉排序樹(shù)1057121418151514185101213725二叉排序樹(shù)例題例(P65)有7個(gè)元素的序列:10571四.二叉樹(shù)的遍歷1.遍歷:按一定次序訪問(wèn)樹(shù)結(jié)構(gòu)中的所有結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。2.遍歷方法先序遍歷中序遍歷后序遍歷26四.二叉樹(shù)的遍歷1.遍歷:按一定次序訪問(wèn)樹(shù)結(jié)構(gòu)中的所有結(jié)先序遍歷方法：根--左--右1)訪問(wèn)根結(jié)點(diǎn)2)先序遍歷左子樹(shù)3)先序遍歷右子樹(shù)根左子樹(shù)右子樹(shù)abc27先序遍歷方法：根--左--右根左子樹(shù)右子樹(shù)abc27中序遍歷方法：左--根---右1)中序遍歷左子樹(shù)2)訪問(wèn)根結(jié)點(diǎn)3)中序遍歷右子樹(shù)根左子樹(shù)右子樹(shù)abc28中序遍歷方法：左--根---右根左子樹(shù)右子樹(shù)abc28后序遍歷方法：左---右---根1)后序遍歷左子樹(shù)2)后序遍歷右子樹(shù)3)訪問(wèn)根結(jié)點(diǎn)根左子樹(shù)右子樹(shù)abc29后序遍歷方法：左---右---根根左子樹(shù)右子樹(shù)abc29二叉樹(shù)的遍歷舉例

oooooooEoCFoABDGHI先序遍歷序列：ABDEGCFHI

填空法:A(B(DE(G)))C(F(HI))中序遍歷序列：DBGEACHFI投影法后序遍歷序列：DGEBHIFCA填空法:(DGEB)(HIFC)A30二叉樹(shù)的遍歷舉例oooooooEoCFoABDGHI先序遍遍歷序列的特性:由同一棵樹(shù)先序和中序遍歷可構(gòu)造唯一的二叉樹(shù)由同一棵樹(shù)后序和中序遍歷可構(gòu)造唯一的二叉樹(shù)例:P69,已知一棵二叉樹(shù)的先序遍歷和中序遍歷序列,構(gòu)造此二叉樹(shù)31遍歷序列的特性:31二叉樹(shù)遍歷算法二叉樹(shù)遍歷方法：遞歸算法非遞歸算法遞歸算法和非遞歸算法中又分：先序法中序法后序法32二叉樹(shù)遍歷算法二叉樹(shù)遍歷方法：32二叉樹(shù)遍歷算法（遞歸算法）二叉鏈表的C語(yǔ)言描述：

structtnode{intdata；structtnode*lc,*rc;}；typedefstructtnodeTNODE;33二叉樹(shù)遍歷算法（遞歸算法）二叉鏈表的C語(yǔ)言描述：33二叉樹(shù)遍歷算法（前序法遞歸程序）voidpreorder_t(TNODE*root){if(root!=NULL){printf(“%d\n”,root->data);if(root->lc!=NULL)preorder_t(root->lc);if(root->rc!=NULL)preorder_t(root->rc);}}

前序遍歷序列為：ABCDEFABCDEF34二叉樹(shù)遍歷算法（前序法遞歸程序）voidpreorder2.3樹(shù)類(lèi)的存儲(chǔ)結(jié)構(gòu)雙親表示:數(shù)組實(shí)現(xiàn)孩子表示:鏈表實(shí)現(xiàn)孩子兄弟表示:二叉鏈表實(shí)現(xiàn)352.3樹(shù)類(lèi)的存儲(chǔ)結(jié)構(gòu)雙親表示:數(shù)組實(shí)現(xiàn)35一.雙親表示法

123456789序號(hào)→結(jié)點(diǎn)→雙親→123456789123456789011223555特點(diǎn)：找雙親容易，找子結(jié)點(diǎn)難存儲(chǔ)數(shù)據(jù)元素結(jié)點(diǎn)同時(shí)存儲(chǔ)雙親結(jié)點(diǎn)的位置36一.雙親表示法123456789序號(hào)→12二.孩子表示法

12345678912345678923NULL45NULL6NULLNULL