【教學(xué)】第6章 樹和二叉樹

第6章樹和二叉樹

樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)6.1樹的定義定義：樹(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)特點(diǎn)：樹中至少有一個(gè)結(jié)點(diǎn)稱為根樹中各子樹是互不相交的集合.A只有一個(gè)根結(jié)點(diǎn)的樹ABCDEFGHIJKLMA為根結(jié)點(diǎn)，其余分為三個(gè)互不相交的子集T1={B,E,F,K,L}T2={C,G}T3={D,H,I,J,M}T1,T2,T3都是根結(jié)點(diǎn)A的子樹，且本身又是一棵樹?！?基本術(shù)語結(jié)點(diǎn)(node)：包括一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)葉子(leaf)：度為0的結(jié)點(diǎn)（或稱終端結(jié)點(diǎn)）分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值孩子(child)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子雙親(parents):(相對孩子)結(jié)點(diǎn)的上層結(jié)點(diǎn)兄弟(sibling)：同一雙親的孩子之間互稱兄弟結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)子孫：某結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)結(jié)點(diǎn)的層次(level)：從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……深度(depth)：樹中結(jié)點(diǎn)的最大層次數(shù)森林(forest)：m(m0)棵互不相交的樹的集合.ADTTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R＝｛H｝，H是如下二元關(guān)系：(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；(2)若D－｛root｝≠φ，則存在D－｛root｝的一個(gè)劃分D1，D2，…，Dm（m>0），對任意j≠k(1≤j,k≤m)有Dj∩Dk=Ф,且對任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素Xi∈Di,有＜root,Xi>∈H;(3)對應(yīng)于D-{root}的劃分,H-{<root,X1>…<root,Xm>}有唯一的一個(gè)劃分H1,H2,…,Hm(m>0),對任意j≠k(1≤j,k≤m)有Hj∩Hk=Ф,且對任意i(1≤i≤m)，Hi是Di上的二元關(guān)系，（Di,{Hi}）是一棵符合本定義的樹，稱為根root的子樹。.基本操作P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);TreeEmpty(T);TreeDepth(T);Root(T);Value(T,cur_e);Assign(T,cur_e,value);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);InsertChild(&T,&p,i,c);DeleteChild(&T,&p,i);TraverseTree(T,Visit());}ADTTree.6.2

二叉樹一、定義二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)AABABABC.ADTBinaryTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D＝φ，則R＝φ，稱BinaryTree為空二叉樹；若D≠φ，則R＝｛H｝，H是如下二元關(guān)系；(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；(2)若D-{root}≠φ,則存在D-{root}＝{Dl,Dr},且Dl∩Dr＝φ；(3)若Dl≠φ，則Dl中存在唯一的元素Xl,<root,Xl>∈H，且存在Dl上的關(guān)系Hl∈H；若Dr≠φ，則Dr中存在唯一的元素Xr，<root,Xr>∈H,且存在Dr上的關(guān)系Hr∈H；H＝{<root,Xl>,<root,Xr>，Hl,Hr};(4)(Dl,{Hl})是一棵符合本定義的二叉樹,稱為根的左子樹(Dr,{Hr})是一棵符合本定義的二叉樹,稱為根的右子樹.基本操作P：InitBiTree(&T);DestroyBiTree(&T)CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);Root(T);Value(T,e);Assign(T,&e,value);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);InsertChild(T,p,LR,c);DeleteChild(T,p,LR);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());}ADTBinaryTree.二、二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)證明：用歸納法證明

i=1時(shí),只有一個(gè)根結(jié)點(diǎn),2i-1=20=1是對的假設(shè)對所有j(1j<i)命題成立，即第j層上至多有

2j-1個(gè)結(jié)點(diǎn)那么，第i-1層至多有2i-2個(gè)結(jié)點(diǎn)又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即2x2i-2=2i-1

故命題得證性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k1)證明：由性質(zhì)1知深度為k的二叉樹最大結(jié)點(diǎn)數(shù)為

kk∑(第i層上的最大結(jié)點(diǎn)數(shù))=∑2i-1=2k–1

i=1i=1.性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)分支進(jìn)入設(shè)B為分支總數(shù)，則n=B+1又：分支由度為1和度為2的結(jié)點(diǎn)射出，B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1.兩種特殊形式的二叉樹滿二叉樹定義：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)1231145891213671014151234567.兩種特殊形式的二叉樹完全二叉樹定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為完全二叉樹特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l或l+1123114589126710123456.性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n

+1證明：設(shè)深度為k，根據(jù)性質(zhì)2和完全二叉樹的定義有2k-1-1<n2k-1或2k-1n<2k于是k-1log2n<k因?yàn)閗是整數(shù)所以k=log2n

+1123114589126710.性質(zhì)5：如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1in)，有：(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2(2)如果2i>n，則結(jié)點(diǎn)i無左孩子；如果2in，則其左孩子是2i(3)如果2i+1>n，則結(jié)點(diǎn)i無右孩子；如果2i+1n，則其右孩子是2i+1123114589126710.三、二叉樹的存儲結(jié)構(gòu)1、順序存儲結(jié)構(gòu)二叉樹的順序存儲表示#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;abckdehilfgj例如：

bt0123456789101112

abcdefghijkl.abcgdef

bt0123456789101112

abcdefgabcdefg順序存儲結(jié)構(gòu)的特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲位置中浪費(fèi)空間，適于存滿二叉樹和完全二叉樹.2、鏈?zhǔn)酱鎯Y(jié)構(gòu)dataPARENTLCHILDRCHILDlchilddataparentrchild含有三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)lchilddatarchild含有兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)ABFGDECA^BC^^DE^F^^G^^二叉鏈表A^^BC^^DE^F^^G^^三叉鏈表.二叉樹的二叉鏈表存儲表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;特點(diǎn)：指針直接表示關(guān)系，操作簡單增加指針域，浪費(fèi)空間，特別是存在多個(gè)空指針域.6.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹遍歷二叉樹(TraversingBinaryTree):按某條搜索路徑巡訪樹的每個(gè)結(jié)點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，從而得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。由二叉樹的遞歸定義可知：二叉樹是由三個(gè)基本單元組成：

根結(jié)點(diǎn)、左子樹、右子樹DLR則可得到六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD先序遍歷(DLR)：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹中序遍歷(LDR)：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹后序遍歷(LRD)：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn).先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）訪問根結(jié)點(diǎn)（2）先序遍歷左子樹（3）先序遍歷右子樹中序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）中序遍歷左子樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn).例：ABCGDEF先序序列：ABDFEGC中序序列：DBFGEAC后序序列：DFGBECA.先序遍歷二叉樹的遞歸算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if（T）{if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPreOrderTraverse(BiTreeT){if（T）{Visit(T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}.中序遍歷算法StatusInOrderTraverse(BiTreeT){if（T）{InOrderTraverse(T->lchild);Visit(T->data);InOrderTraverse(T->rchild);}}后序遍歷算法StatusPostOrderTraverse(BiTreeT){if（T）{PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);Visit(T->data);}}.遍歷過程演示：-*cab-*c^^a^^b^^bt-*bac先序序列：-*abc.遍歷過程演示：-*cab-*c^^a^^b^^bt-*bac先序序列：-*abca*b-c中序序列：a*b-c.遍歷過程演示：-*cab-*c^^a^^b^^bt-*bac先序序列：-*abca*b-c中序序列：a*b-cab*c-中序序列：ab*c-.中序遍歷的非遞歸算法StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);Push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);Pop(S,p);if(!StackEmpty(S)){Pop(S,p);if(!Visit(p->data))returnERROR;Push(S,p->rchild);}}returnOK;}.中序遍歷的非遞歸算法StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;}.按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹TStatusCreateBiTree(BiTree&T){scanf(&ch);if(ch==‘’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}.6.4樹與森林一、樹的存儲結(jié)構(gòu)1、雙親表示法用結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn):找雙親容易，找孩子難ABCHDEIFGA-1B0C0D1E1F2G4H4I4012345678dataparent.樹的雙親表示#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;}PTNode;

typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;}PTree;例：求結(jié)點(diǎn)t[i]的長子IntFirstChild(Ptreet,inti){for(j=i+1;j<t.n;j++)if(t.nodes[j].parent==i)return(j);return(-1);}.2、孩子表示法多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹的根結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度ddatachild1child2……childd結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，

degree為該結(jié)點(diǎn)的度d’datachild1child2……childd’degree浪費(fèi)空間操作不便.ABCHDEIFG孩子鏈表表示：ABCD^EF^G^H^I^012345678134^678^5^2^datafirstchild如何找雙親結(jié)點(diǎn).ABCHDEIFG孩子鏈表表示：A-1B0C0D1^E1F2^G4^H4^I4^012345678134^678^5^2^dataparentfirstchild.樹的孩子鏈表存儲表示typedefstructCTNode{intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;Childptrfirstchild;}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根的位置}CTree;.3、孩子兄弟表示法：----二叉鏈表表示法用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;firstchilddatanextsibling.例：ABCHDEIFGA

B

C

D

E

F

G

H

I

^^^^^^^^^.二、森林與二叉樹的轉(zhuǎn)換借助于二叉鏈表存儲結(jié)構(gòu)實(shí)現(xiàn)樹與二叉樹的轉(zhuǎn)換ACBED樹A^^BC^D^^E^ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^存儲解釋存儲解釋.加線：在兄弟之間加一連線刪線：對每個(gè)結(jié)點(diǎn)，除了其長子孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針旋轉(zhuǎn)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將樹轉(zhuǎn)換成二叉樹.

從樹與二叉樹的轉(zhuǎn)換可知：任何一棵和樹對應(yīng)的二叉樹，其右子樹必為空，若把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹根結(jié)點(diǎn)的兄弟，則可導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。森林轉(zhuǎn)換成二叉樹如果F＝｛T1，T2，…Tm｝是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B＝（root,LB,RB）。（1）若F為空，即m＝0，則B為空樹（2）若F非空，即m≠0，則B的根root即為森林中第一棵樹的根ROOT（T1）；B的左子樹LB是從T1中根結(jié)點(diǎn)的子樹森林F1＝｛T11，T12，…T1m1｝轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F`=｛T2，T3，…Tm｝轉(zhuǎn)換而成的二叉樹。.二叉樹轉(zhuǎn)換成森林如果B＝（root,LB,RB）是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F＝｛T1，T2，…Tm｝；（1）若B為空，則F為空；（2）若B非空，則F中第一棵樹T1的根ROOT（T1）即為二叉樹B的根root；T1中根結(jié)點(diǎn)的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的森林；F中除T1之外其余樹組成的森林F`=｛T2，T3，…Tm｝是由B