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

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

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

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

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

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

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

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

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

123865741091112131415第3層有23-1個(gè)結(jié)點(diǎn).深度為4,則最多有24-1個(gè)結(jié)點(diǎn).14123865741091112131415第3層有23-15.二叉樹的基本運(yùn)算1.setnull(BT)將二叉樹BT置空2.root(x)x所在二叉樹的根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的左子樹del_rchild(BT,x)刪除x的右子樹7.TRAVERSE(BT）遍歷樹T155.二叉樹的基本運(yùn)算1.setnull(BT)二.二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)

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

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

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

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滿二叉樹存儲舉例143257612三.特殊二叉樹---完全二叉樹深度為k的二叉樹T,每層結(jié)點(diǎn)數(shù)目若滿足:第i層(1≤i≤k-1)的結(jié)點(diǎn)個(gè)數(shù)均為2i-1第k層從右邊連續(xù)缺若干個(gè)結(jié)點(diǎn)這樣的樹稱為完全二叉樹。特點(diǎn):葉結(jié)點(diǎn)只能出現(xiàn)在層次最大的兩層上.

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

oooooooEoCFoABDGHI先序遍歷序列：ABDEGCFHI

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

structtnode{intdata；structtnode*lc,*rc;}；typedefstructtnodeTNODE;33二叉樹遍歷算法（遞歸算法）二叉鏈表的C語言描述：33二叉樹遍歷算法（前序法遞歸程序）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二叉樹遍歷算法（前序法遞歸程序）voidpreorder2.3樹類的存儲結(jié)構(gòu)雙親表示:數(shù)組實(shí)現(xiàn)孩子表示:鏈表實(shí)現(xiàn)孩子兄弟表示:二叉鏈表實(shí)現(xiàn)352.3樹類的存儲結(jié)構(gòu)雙親表示:數(shù)組實(shí)現(xiàn)35一.雙親表示法

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

12345678912345678923NULL45NULL6NULLNULL