樹二叉樹樹森林和二叉樹轉(zhuǎn)換樹應(yīng)用

樹二叉樹樹森林和二叉樹轉(zhuǎn)換樹應(yīng)用2023/3/132樹和森林的概念樹的定義

樹是由n(n

0)個(gè)結(jié)點(diǎn)組成的有限集合。如果n=0，稱為空樹；如果n>0，則

有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；

除根以外的其它結(jié)點(diǎn)劃分為m(m

0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。2023/3/133樹的表示

樹型表示bacghdefij2023/3/134凹入表表示abdeijfcgh2023/3/135嵌套集合表示嵌套括號表示ijdfghabcea(b(d,e(i,j),c(g,h)))2023/3/136結(jié)點(diǎn)(node)結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)的子樹個(gè)數(shù)分支(branch)結(jié)點(diǎn)度不為0的結(jié)點(diǎn)葉(leaf)結(jié)點(diǎn)度為0的結(jié)點(diǎn)子女(child)結(jié)點(diǎn)某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)雙親(parent)結(jié)點(diǎn)某個(gè)結(jié)點(diǎn)是其子樹之根的雙親2023/3/137兄弟(sibling)結(jié)點(diǎn)具有同一雙親的所有結(jié)點(diǎn)祖先(ancestor)結(jié)點(diǎn)若樹中結(jié)點(diǎn)k到ks存在一條路徑，則稱k是ks的祖先子孫(descendant)結(jié)點(diǎn)若樹中結(jié)點(diǎn)k到ks存在一條路徑，則稱ks是k的子孫結(jié)點(diǎn)所處層次(level)根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為雙親結(jié)點(diǎn)的層數(shù)加1樹的高度(depth)樹中結(jié)點(diǎn)的最大層數(shù)樹的度(degree)

有序樹子樹的次序不能互換無序樹子樹的次序可以互換森林互不相交的樹的集合2023/3/138樹的基本操作1、初始化2、求指定結(jié)點(diǎn)所在樹的根結(jié)點(diǎn)3、求指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)4、求指定結(jié)點(diǎn)的某一孩子結(jié)點(diǎn)5、求指定結(jié)點(diǎn)的最右邊兄弟結(jié)點(diǎn)6、將一棵樹插入到另一樹的指定結(jié)點(diǎn)下作為它的子樹7、刪除指定結(jié)點(diǎn)的某一子樹8、樹的遍歷2023/3/139二叉樹(BinaryTree)二叉樹的定義二叉樹的五種不同形態(tài)

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。2023/3/1310性質(zhì)1

若二叉樹的層次從1開始,則在二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)。(i

0)二叉樹的性質(zhì)證明：i=1時(shí)，有2i-1=

20=1，成立假定：i=k時(shí)性質(zhì)成立；當(dāng)i=k+1時(shí)，第k+1的結(jié)點(diǎn)至多是第k層結(jié)點(diǎn)的兩倍，即總的結(jié)點(diǎn)個(gè)數(shù)至多為2×2k-1=

2k故命題成立2023/3/1311性質(zhì)2

高度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)。

(k

1)證明：僅當(dāng)每一層都含有最大結(jié)點(diǎn)數(shù)時(shí)，二叉樹的結(jié)點(diǎn)數(shù)最多，利用性質(zhì)1可得二叉樹的結(jié)點(diǎn)數(shù)至多為：20+21+22+23+

…

+2k-1=2k－12023/3/1312性質(zhì)3

對任何一棵二叉樹,如果其葉結(jié)點(diǎn)個(gè)數(shù)為

n0,度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為n2,則有

n0＝n2＋1證明：1、結(jié)點(diǎn)總數(shù)為度為0的結(jié)點(diǎn)加上度為1的結(jié)點(diǎn)再加上度為2的結(jié)點(diǎn)：

n=n0+n1+n22、另一方面，二叉樹中一度結(jié)點(diǎn)有一個(gè)孩子，二度結(jié)點(diǎn)有二個(gè)孩子，根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子，因此，結(jié)點(diǎn)總數(shù)為：

n=n1+2n2+13、兩式相減，得到：

n0=n2+12023/3/1313定義1

滿二叉樹(FullBinaryTree)

一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。定義2

完全二叉樹(CompleteBinaryTree)

若設(shè)二叉樹的高度為h，則共有h+1層。除第h層外，其它各層(0h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。2023/3/1314性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為log2n

+1證明：設(shè)完全二叉樹的高度為h，則有

2h-1-1<n

2h-12h-1<=n

<2h

取對數(shù)h–1<log2(n)<h

2023/3/1315性質(zhì)5

如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號1,2,…,n-1,n，然后按此結(jié)點(diǎn)編號將樹中各結(jié)點(diǎn)順序地存放于一個(gè)一維數(shù)組中,并簡稱編號為i的結(jié)點(diǎn)為結(jié)點(diǎn)i(1

i

n)。則有以下關(guān)系：若i==1,則i無雙親若i>1,則i的雙親為i/2

若2*i<=n,則i的左子女為2*i；否則，i無左子女，必定是頁結(jié)點(diǎn)，二叉樹中i>

n/2

的結(jié)點(diǎn)必定是頁結(jié)點(diǎn)若2*i+1<=n,則i的右子女為2*i+1，否則，i無右子女若i為奇數(shù),且i不為1，則其左兄弟為i-1，否則無左兄弟；若i為偶數(shù),且小于n，則其右兄弟為i+1，否則無右兄弟

i所在層次為log2(i)+12023/3/131612435689107111213141516172023/3/1317完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示二叉樹的存儲數(shù)組表示2023/3/1318

單支樹由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費(fèi)很多存儲空間，單支樹就是一個(gè)極端情況。2023/3/1319鏈表表示2023/3/1320二叉樹鏈表表示的示例2023/3/1321二叉鏈表的靜態(tài)結(jié)構(gòu)2023/3/1322樹結(jié)點(diǎn)的描述typedefintdatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;2023/3/1323二叉樹的生成bitree*Q[maxsize];bitree*CREATREE(){charch;intfront,rear;bitree*root,*s;root＝NULL;front＝1;rear＝0;ch＝getchar();while(ch!=‘#’){s＝NULL;if(ch!=‘@’){s＝(bitree*)malloc(sizeof(bitree));s->data＝ch;s->lchild＝NULL;s->rchild＝NULL;}2023/3/1324rear++;Q[rear]＝s;if(rear==1)root＝s;else{if(s&&Q[front])if(rear%2==0)Q[front]->lchild＝s;elseQ[front]->rchild＝s;if(rear%2==1)front++;}ch=getchar();}returnroot;}2023/3/1325中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(diǎn)(V)；中序遍歷右子樹(R)。遍歷結(jié)果

a+b*c

-

d

-

e/f中序遍歷表達(dá)式語法樹二叉樹的遍歷2023/3/1326中序遍歷算法INORDER(bitree*cnt){if(cnt){INORDER(t->lch);printf(“\t%c\n”,t->data);INORDER(t->rch);}}2023/3/1327中序遍歷二叉樹的遞歸過程圖解2023/3/1328前序遍歷前序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則

訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結(jié)果-+a*b

-

cd/ef2023/3/1329后序遍歷后序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(diǎn)(V)。遍歷結(jié)果abcd

-*+ef/-2023/3/1330層序遍歷層序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則，如隊(duì)列不空，循環(huán)：根結(jié)點(diǎn)入隊(duì)，并作為當(dāng)前結(jié)點(diǎn)；將當(dāng)前結(jié)點(diǎn)的左右孩子入隊(duì)；做出隊(duì)操作，隊(duì)首元素作為當(dāng)前結(jié)點(diǎn)最后，出隊(duì)序列就是層序遍歷序列遍歷結(jié)果-+/a*ef

b

-cd

2023/3/1331例：在二叉樹中查找具有給定值的結(jié)點(diǎn)bitreefindnode(bitree*t,datatypex){if(t==NULL)return(NULL);elseif(t->data==x)return(t);elsereturn(findnode(t->lchild)||findnode(t->rchild))}2023/3/1332例：給定一棵二叉樹，輸出其嵌套括號表示voidprint(bitree*t){if(t){printf(“%d”,t->data);if(t->lchild||t->rchild){printf(“(”);printf(lchild);if(t->rchild)printf(“,”);print(rchild);printf(“)”);}}}2023/3/1333例：求二叉樹的深度voiddepth(bitree*t){intdep1,dep2;if(t==NULL)return(0);else{dep1=depth(t->lchild);dep2=depth(t->rchild);if(dep1>dep2)return(dep1+1);elsereturn(dep2+1);}}2023/3/1334例：證明：一棵二叉樹的前序序列和中序序列可以唯一的確定這棵二叉樹。用歸納法證明：1、當(dāng)n=1時(shí)，結(jié)論顯然成立；2、假定當(dāng)n<=k時(shí)，結(jié)論成立；3、當(dāng)n=k+1時(shí)，假定前序序列為和中序序列分別為：

{a1，…，am}和{b1，…

，bm}2023/3/1335

如中序序列中與前序序列a1相同的元素為bj。j=1時(shí)，二叉樹無左子樹，由{a2，…，am}和{b2，…

，bm}可以唯一的確定二叉樹的右子樹；j=m時(shí)，二叉樹無右子樹，由{a2，…，am}和{b1，…

，bm-1}可以唯一的確定二叉樹的左子樹；如2<=j<=m-1，則子序列{a2，…，aj}和{b1，…

，bj-1}唯一的確定二叉樹的左子樹；子序列{aj+1，…，am}和{bj+1，…

，bm}唯一的確定二叉樹的右子樹2023/3/1336{a1，a2

，…，aj，aj+1，…，am}{b1，…

，bj-1，bj，bj+1，…

，bm}唯一的確定左子樹唯一的確定右子樹個(gè)數(shù)相同2023/3/1337

由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹過程如下：2023/3/1338

如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。

前序序列：1，2，3，4，5，6，7，8，9

中序序列a：3，2，5，4，1，6，8，7，9

中序序列b：4，3，5，2，1，7，6，8，92023/3/1339

例如，有3個(gè)數(shù)據(jù){1,2,3}，可得5種不同的二叉樹。它們的前序排列均為

123，中序序列可能是

123，132，213，231，321。

有0個(gè),1個(gè),2個(gè),3個(gè)結(jié)點(diǎn)的不同二叉樹如下2023/3/1340樹的存儲表示廣義表表示樹的廣義表表示

(結(jié)點(diǎn)的utype域沒有畫出)樹與森林2023/3/1341雙親表示2023/3/1342樹的存儲－－雙親鏈表表示法#definemaxnode32typedefstructbnode{datatypedata;//數(shù)據(jù)域

intparent;//游標(biāo)域}ptree;ptreeT[maxnode];

2023/3/1343求長子的算法intFIRSTCHILD(ptreeT[],inti){intj;for(j=i+1;j<maxnode;j++)if(T[j].parent==i)return(j);return(0);}2023/3/1344孩子鏈表示ABCDEFGHIJABCDEFGGIJ2348910567123456789102023/3/1345樹的存儲－－孩子鏈表表示法typedefstructcnode{intchild;//孩子結(jié)點(diǎn)序號

structcnode*next;}link;

typedefstructdnode{datatypedata;link*headptr;}ctree;ctreeT[maxnode];2023/3/1346雙親-孩子鏈表示ABCDEFGHIJA0B1C1D1E2F2G3G4I4J42348910567123456789102023/3/1347左孩子-右兄弟表示法第一種解決方案第二種解決方案樹的左子女-右兄弟表示datachild1child2child3childd

datafirstChildnextSibling2023/3/1348森林與二叉樹的轉(zhuǎn)換森林與二叉樹的對應(yīng)關(guān)系2023/3/1349(1)森林轉(zhuǎn)化成二叉樹的規(guī)則

若F為空，即n=0，則對應(yīng)的二叉樹B為空二叉樹。若F不空，則對應(yīng)二叉樹B的根root(B)是F中第一棵樹T1的根root(T1)；其左子樹為B(T11,T12,…,T1m)，其中，T11,T12,…,T1m是root(T1)的子樹；其右子樹為B(T2,T3,…,Tn)，其中，T2,T3,…,Tn是除T1外其它樹構(gòu)成的森林。2023/3/1350

2023/3/1351森林轉(zhuǎn)換為樹的算