數(shù)據(jù)結(jié)構(gòu)（雙語）15-16-BinaryTree

DataStructure

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)與信息技術(shù)系袁瑩2019年04月19日LogicalStructure（邏輯結(jié)構(gòu)）Linear（list:stack/queue）StorageStructure（存儲(chǔ)結(jié)構(gòu)）sequential&linkedOperate（運(yùn)算）InsertDeleteFindReviewReview線性表(LinearList)分類存儲(chǔ)結(jié)構(gòu)普通線性表(List)特殊線性表?xiàng)?Stack)隊(duì)列(Queue)順序結(jié)構(gòu)(Sequential)(數(shù)組實(shí)現(xiàn))順序表順序棧順序隊(duì)列（循環(huán)隊(duì)列）鏈?zhǔn)浇Y(jié)構(gòu)(Linked)(指針實(shí)現(xiàn))鏈表鏈棧鏈隊(duì)（單循環(huán)鏈表）TimeComplexity4.1Preliminaries4.1.1ImplementationofTrees4.1.2TreeTraversalswithanApplication4.2BinaryTrees4.2.1Implementation4.2.2ExpressionTrees4.2.3TraversalsChapter4Trees4.3TheSearchTreeADT—BinarySearch

Tree 4.3.1MakeEmpty

4.3.2Find

4.3.3FindMinandFindMax

4.3.4Insert

4.3.5Delete

4.3.6Average-CaseAnalysisChapter4TreesCHAPTER4TREES§1Preliminaries1.TerminologyLinealTree（直系樹）PedigreeTree（家譜樹）(binarytree)【Definition】Atreeisacollectionofnodes.Thecollectioncanbeempty;otherwise,atreeconsistsof(1)adistinguishednoder,calledtheroot;(2)andzeroormorenonempty(sub)trees

T1,,Tk,eachofwhoserootsareconnectedbyadirectededgefromr.Note:Subtreesmustnotconnecttogether.Thereforeeverynodeinthetreeistherootofsomesubtree.ThereareedgesinatreewithNnodes.Normallytherootisdrawnatthetop.N

1ACBDGFEHIJMLKleaf(terminalnode)::=anodewithdegree0(nochildren).parent::=anodethathassubtrees.children::=therootsofthesubtreesofaparent.siblings::=childrenofthesameparent.ACBDGFEHIJMLKdegreeofanode::=numberofsubtreesofthenode.Forexample,degree(A)=3,degree(F)=0.degreeofatree::=

Forexample,degreeofthistree=3.ACBDGFEHIJMLKdepthofni::=lengthoftheuniquepathfromtheroottoni.Depth(root)=0.pathfromn1tonk

::=a(unique)sequenceofnodesn1,n2,…,nk

suchthatniistheparentofni+1for1i<k.lengthofpath::=numberofedgesonthepath.heightofni::=lengthofthelongestpathfromnitoaleaf.Height(leaf)=0,andheight(D)=2.ACBDGFEHIJMLKancestorsofanode::=allthenodesalongthepathfromthenodeuptotheroot.（祖先）descendantsofanode::=allthenodesinitssubtrees.（后裔）height(depth)ofatree::=height(root)=depth(deepestleaf).ForthetreeinFig4.59,

a.Whichnodeistheroot?

b.Whichnodesareleaves?

Foreachnode(E)inthetree:

a.Nametheparentnode.

b.Listthechildren.

c.Listthesiblings.

d.Computethedepth.

e.Computetheheight.在一棵度為3的樹中，度為3的節(jié)點(diǎn)數(shù)為2個(gè)，度為2的節(jié)點(diǎn)數(shù)為1個(gè)，度為1的節(jié)點(diǎn)數(shù)為2個(gè)，則度為0的節(jié)點(diǎn)數(shù)為（）。2.ImplementationofTrees

ListRepresentationACBDGFEHIJMLK(A)(A(B,C,D))(A(B(E,F),C(G),D(H,I,J)))(A(B(E(K,L),F),C(G),D(H(M),I,J)))ABCDEFGHIJKLMSothesizeofeachnodedependsonthenumberofbranches.Hmmm...That’snotgood.

FirstChild-NextSiblingRepresentationFirstChildNextSiblingElementACBDGFEHIJMLKNACBNDENKNNFNNGHNINNJNNLNNMAnswer:Therepresentationisnotuniquesincethechildreninatreecanbeofanyorder.§1PreliminariesAsk:Whethertherepresentationisunique?typedefstructTreeNode*PtrToNode;structTreeNode{ ElementTypeElement; PtrToNodeFirstChild; PtrToNodeNextSibling;};

Node

declarations

for

trees§1Preliminaries〖Example〗Directorylistinginahierarchicalfilesystem.Listingformat:filesthatareofdepthdi

willhavetheirnamesindentedbyditabs./usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnixdirectory3.TreeTraversalswithanApplication/usrmarkbook Ch1.c Ch2.c Ch3.ccourse cop3530 fall96 syl.r spr97 syl.r sum97 syl.r

hw.calexhw.cbillworkcourse cop3212 fall96 grades p1.r p2.r fall97 p2.r p1.r gradesAlgorithm：staticvoidListDir(DirectoryOrFileD,intDepth){

if(Disalegitimateentry) { PrintName(D,Depth);

if(Disadirectory)

foreachchild,C,ofD ListDir(C,Depth+1); }}3.TreeTraversalswithanApplicationpreordertraversalT(N)=O(N)staticvoidListDir(DirOrFileD,intDepth){

if(Disalegitimateentry){PrintName(D,Depth);

if(Disadirectory)

for(eachchildCofD)ListDir(C,Depth+1);}}Note:

Depthisaninternalvariableandmustnotbeseenbytheuserofthisroutine.Onesolutionistodefineanotherinterfacefunctionasthefollowing:voidListDirectory(DirOrFileD){ ListDir(D,0);}T(N)=O(N)preordertraversal/usrmarkbook Ch1.c Ch2.c Ch3.ccourse cop3530 fall96 syl.r spr97 syl.r sum97 syl.r

hw.calexhw.cbillworkcourse cop3212 fall96 grades p1.r p2.r fall97 p2.r p1.r grades〖Example〗Calculatingthesizeofadirectory./usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnixdirectorywithfilesizes11111111111111132468152341279staticintSizeDir(DirOrFileD){

intTotalSize;TotalSize=0;if(Disalegitimateentry){TotalSize=FileSize(D);if(Disadirectory)

for(eachchildCofD)TotalSize+=SizeDir(C);}/*endifDislegal*/

returnTotalSize;}T(N)=O(N) Ch1.c 3 Ch2.c 2 Ch3.c 4

book 10 syl.r 1 fall96 2 syl.r 5 spr97 6 syl.r 2 sum97 3 cop3530 12 course 13 hw.c 6 mark 30 hw.c 8 alex 9 work 1 grades 3 p1.r 4 p2.r 1 fall96 9 p2.r 2 p1.r 7 grades 9 fall97 19 cop3212 29 course 30 bill 32/usr 72

postordertraversalWritethepreorderandpostordertraversalofthefollowingtree.ACBDGFEHIJMLKPreorder：ABEKLFCGDHMIJPostorder：KLEFBGCMHIJDAReviewACBDGFEHIJMLKdegree(A),degree(Tree)leaf(terminalnode)Parentchildrensiblings(H)path(fromAtoM)lengthofpath(fromAtoM)level(K)depth(H)height(B)height(Tree)/depth(Tree)4.2BinaryTrees4.2.1Implementation4.2.2ExpressionTrees4.2.3Traversals*HuffmantreeContents4.2BinaryTrees【Definition】Abinarytreeisatreeinwhichnonodecanhavemorethantwochildren.NACBNDENKNNFNNGHNINNJNNLNNMRotatetheFirstChild-NextSiblingtreeclockwiseby45.45NACBNDENKNNFNNGHNINNJNNLNNMLeftRightElementLeftRightBinaryTreewithNnodeswouldrequireN+1

NULLpointers.typedefstructTreeNode*PtrToNode;typedefstructPtrToNodeTree;structTreeNode{ ElementTypeElement; TreeLeft;

TreeRight;};4.2.1ImplementationArrayimplementation?ABCDEFGH012345678下標(biāo)結(jié)點(diǎn)ABDCE#####F01234567891011下標(biāo)結(jié)點(diǎn)Thei-thlevelofbinarytreehasmost2i-1(i>=1)nodes.Themaximumnumberofnodesinabinarytreeofheighth(ordepthk)is

2h+1-1(or2k+1-1).Inabinarytree,iftherearen0nodesofdegree0,n2nodesofdegree2,thenn0=n2+Implementation Notices:FullBinaryTree&CompleteBinaryTree(a)FullBinaryTree(b)CompleteBinaryTree(c)noncomplete binarytree具有N個(gè)節(jié)點(diǎn)的完全二叉樹的深度為（?log2N?）？4.2.1ImplementationCompleteBinaryTree（1）若結(jié)點(diǎn)i有父親（即i>1），則父親的序號(hào)為?i/2?。（2）若結(jié)點(diǎn)i有左孩子（即2i<=n時(shí)），則左孩子為2i。（3）若結(jié)點(diǎn)i有右孩子（即2i+1<=n時(shí)），則右孩子為2i+1。（4）當(dāng)i為偶數(shù)且i≠n時(shí)，它有右兄弟，右兄弟為i+1。（5）當(dāng)i為奇數(shù)且i≠1時(shí)，它有左兄弟，左兄弟為i-1。4.2.1ImplementationExpressionTrees(syntaxtrees)〖Example〗Givenaninfixexpression:

A+BCD+ADBCWereadourexpressiononesymbolatatime.Ifthesymbolisanoperand,wecreateaone-nodetreeandpushapointertoitontoastack.Ifthesymbolisanoperator,wepoppointerstotwotreesT1andT2fromthestack(T1ispoppedfirst)andformanewtreewhoserootistheoperatorandwhoseleftandrightchildrenpointtoT2andT1,respectively.Apointertothistreeisthenpushedontothestack.ConstructinganExpressionTree(frompostfixexpression)4.2.2ExpressionTrees〖Example〗

(a

+

b)*

(

c

*(d

+

e

))=ab

+

cde

+**abT2aT1b+cdec+T1T2de+abc+deT1T2*+abc+deT1T2**4.2.2ExpressionTrees4.2.2ExpressionTrees(syntaxtrees)〖Example〗Givenaninfixexpression:

A+BCD+ADBCConstructinganExpressionTree(frompostfixexpression)〖Example〗

(a

+

b)*

(

c

*(d

+

e

))=ab

+

cde

+**abT2aT1b+cdec+T1T2de+abc+deT1T2*+abc+deT1T2**operandoperator*bcf*de+a+*g+4.2.3TreeTraversalsoperatoroperandinordertraversalleftnoderightpostordertraversalleftrightnodepreordertraversalnodeleftright(a+(b*c))+(((d*e)+f)*g)abc*+de*f+g*+++a*bc*+*defgAlgorithm1：

PreorderTraversalvoidPreOrder(BiTree*T) /*前序遍歷二叉樹*/{ if(T) /*當(dāng)二叉樹非空，進(jìn)入遞歸過程；

否則，遍歷運(yùn)算結(jié)束*/{

printf("%c",T->Element); /*訪問根結(jié)點(diǎn)*/PreOrder(T->Left);/*前序遍歷左子樹*/PreOrder(T->Right);/*前序遍歷右子樹*/}}4.2.3TreeTraversals——visiteachnodeexactlyonce4.2.3TreeTraversalsAlgorithm2：PostorderTraversalvoidPostOrder(BiTree*T) /*后序遍歷二叉樹*/{ if(T){PostOrder(T->Left); /*后序遍歷左子樹*/PostOrder(T->Right); /*后序遍歷右子樹*/printf("%c",T->Element); /*訪問根結(jié)點(diǎn)*/}}Algorithm3：InorderTraversalvoidInOrder(BiTree*T) /*中序遍歷二叉樹*/{ if(T){InOrder(T->Left); /*中序遍歷左子樹*/printf("%c",T->Element); /*訪問根結(jié)點(diǎn)*/InOrder(T->Right); /*中序遍歷右子樹*/}}4.2.3TreeTraversalsbc*de+a*-Exercise1:Givetheinfix,postfix,andprefixexpressionscorrespondingtothistree:(1)((a*b)*(c+d))-e.(2)ab*cd+*e-.(3)-**ab+cde.4.2.3TreeTraversalsExercise2:Givethepreorder,inorder,postordertraversalresultscorrespondingtothistree:(1)ABCFGDE(2)CBGFADE(3)CGFBEDA4.2.3TreeTraversals(1)GiventhepreordertraversalsequenceABDCEFHGandtheinordertraversalsequenceBDAFHEGC,thecorrespondingpostordertraversalsequenceis().①DBAHFGCE;②BDHFGECA;③DBHFGECA;④DBCFHEGA(2)Themaximumnumberofnodesinabinarytreeofheightkis①2k+1–1②2k–1③2k-1–1④2k+1HomeworkP123二、選擇題三、填空題四、簡(jiǎn)答題3（1）*Huffmantree一、哈夫曼樹的定義及建立

結(jié)點(diǎn)的路徑長(zhǎng)度（lengthofpath）就是從根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度，其值為路經(jīng)上的邊數(shù)。賦予了權(quán)值的結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)值的乘積即為結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度（WeightedPathLengthofNode）。樹的帶權(quán)路徑長(zhǎng)度（WeightedPathLengthofTree，縮寫為WPL）定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為：其中n表示葉子結(jié)點(diǎn)數(shù)，wi表示第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li代表第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。WPLa=2×2+3×2+6×2+8×2=38WPLb=8×1+6×2+2×3+3×3=35WPLc=2×1+6×3+8×3+3×2=50WPLd=8×1+2×3+3×3+6×2=35哈夫曼樹（HuffmanTree）又稱最優(yōu)二叉樹，是在含有n個(gè)葉子結(jié)點(diǎn)，權(quán)值分別為w1，w2，……，wn的所有二叉樹中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹。哈夫曼（D.A.Huffman）在上世紀(jì)五十年代初便提出了一個(gè)非常簡(jiǎn)單的算法來建立哈夫曼樹，其算法描述如下：（1）將給定的n個(gè)權(quán)值{w1，w2，...，wn}作為n個(gè)根結(jié)點(diǎn)的權(quán)值，構(gòu)造一個(gè)具有n棵二叉樹的森林{T1，T2，...，Tn}，其中每棵二叉樹只有一個(gè)根結(jié)點(diǎn)；（2）在森林中選取兩棵根點(diǎn)權(quán)值最小的二叉樹分別作為左、右子樹，增加一個(gè)新結(jié)點(diǎn)作為根，從而將兩棵樹合并成一棵樹，新根結(jié)點(diǎn)的權(quán)值為左右子樹根結(jié)點(diǎn)權(quán)值之和。森林中因此也減少了一棵樹；（3）重復(fù)上面步驟（2）的處理過程，直到森林中只有一棵二叉樹為止，這棵二叉樹就是哈夫曼樹。Huffmantree從哈夫曼樹構(gòu)造過程和生成結(jié)果可知，哈夫曼樹具有以下特點(diǎn)：（1）哈夫曼樹不唯一。（2）哈夫曼樹中只包含度為0和度為2的結(jié)點(diǎn)。（3）樹中權(quán)值越大的葉子結(jié)點(diǎn)離根結(jié)點(diǎn)越近。例

假設(shè)樹中葉子結(jié)點(diǎn)的權(quán)值為{5,29,7,8,14,23,3,11}，構(gòu)造一棵哈夫曼樹。（1）將給定的8個(gè)權(quán)值作為根結(jié)點(diǎn)，構(gòu)造具有8棵樹的森林（2）從森林中選取根點(diǎn)權(quán)值最小的兩棵二叉樹3、5，分別作為左右子樹，構(gòu)造一棵新的二叉樹，新樹根點(diǎn)權(quán)值為8，森林中減少一棵樹。（3）重復(fù)步驟（2），直到森林中只剩一棵二叉樹為止。Huffmantree方便查找父親，將哈夫曼樹的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)為三叉鏈表。每個(gè)結(jié)點(diǎn)包含四個(gè)域：weight為結(jié)點(diǎn)的權(quán)值，lchild、rchild、parent分別為左、右孩子和父親結(jié)點(diǎn)的指針。含有N個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2N-1個(gè)結(jié)點(diǎn)，由此可定義一個(gè)長(zhǎng)度為2N-1的數(shù)組tree來存儲(chǔ)哈夫曼樹，下標(biāo)從1開始，0代表指針空（NULL）。weightparentlchildrchildtypedefstruct /*哈夫曼樹結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)*/{ floatweight; /*結(jié)點(diǎn)的權(quán)值*/ intparent; /*雙親在數(shù)組中的下標(biāo)*/ intlchild,rchild;/*左右孩子在數(shù)組中的下標(biāo)*/}HufmTree;HufmTreetree[2N];在上述存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)哈夫曼算法的過程如下：（1）將哈夫曼樹數(shù)組tree中的2N-1個(gè)結(jié)點(diǎn)初始化：即將各結(jié)點(diǎn)的權(quán)值、雙親、左孩子、右孩子均置為0。（2）讀入N個(gè)葉子結(jié)點(diǎn)的權(quán)值，分別存入數(shù)組tree[i]（1≤i≤N）的權(quán)值域中，構(gòu)造包含N棵樹的初始森林，森林中的每棵樹只有一個(gè)根結(jié)點(diǎn)。（3）循環(huán)N-1次，對(duì)森林中的樹進(jìn)行N-1次合并，產(chǎn)生N-1個(gè)新結(jié)點(diǎn)，依次放入數(shù)組tree[i]中（N+1≤i≤2N-1）。每次合并的步驟是：1）在當(dāng)前森林的所有結(jié)點(diǎn)tree[j]（1≤j≤i-1）中，選取具有最小權(quán)值和次小權(quán)值的兩個(gè)根結(jié)點(diǎn)（parent域?yàn)?的結(jié)點(diǎn)），分別用p1和p2記住這兩個(gè)根結(jié)點(diǎn)在數(shù)組tree中的下標(biāo)。2）將根為tree[p1]和tree[p2]的兩棵樹合并，使其成為新結(jié)點(diǎn)tree[i]的左、右孩子，得到一棵以新結(jié)點(diǎn)tree[i]為根的二叉樹即將tree[i].weight賦值為tree[p1].weight和tree[p2].weight之和tree[i]的左指針賦值為p1；tree[i]的右指針賦值為p2；同時(shí)將tree[p1]和tree[p2]的雙親域均賦值為i，使其指向新結(jié)點(diǎn)tree[i]即它們?cè)诋?dāng)前森林中已不再是根結(jié)點(diǎn)。

以（2,3,6,8）為例，分析哈夫曼樹構(gòu)造的實(shí)現(xiàn)算法數(shù)組下標(biāo)weightparentlchildrchild012000230003600048000500006000070000二、哈夫曼編碼及譯碼在進(jìn)行文字傳輸時(shí)，數(shù)據(jù)通信的發(fā)送方需要將原文中的每一個(gè)文字轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制0、1序列（編碼）進(jìn)行發(fā)送，接收方接收到二進(jìn)制的0、1串后再還原成原文（譯碼）。其編碼和譯碼的過程如下所示：原文

電文（二進(jìn)制的0、1序列）

原文常用的編碼方式有兩種：等長(zhǎng)編碼和不等長(zhǎng)編碼。等長(zhǎng)編碼：ASCⅡ碼，其特點(diǎn)是每個(gè)字符的編碼長(zhǎng)度相同。編碼簡(jiǎn)單且具有唯一性，當(dāng)字符集中的字符在電文中出現(xiàn)的頻度相等時(shí)，它是最優(yōu)的編碼。不等長(zhǎng)編碼：字符的編碼長(zhǎng)度不等，因此稱這種編碼方式為不等長(zhǎng)編碼。為了使譯碼唯一，則要求字符集中任一字符的編碼都不是其他字符編碼的前面一部分，這種編碼叫做前綴（編）碼。二、哈夫曼編碼及譯碼利用二叉樹來對(duì)葉子結(jié)點(diǎn)進(jìn)行編碼，所得的編碼一定為前綴碼。若要使報(bào)文總長(zhǎng)最短，則利用哈夫曼樹對(duì)葉子結(jié)點(diǎn)進(jìn)行編碼一定是最優(yōu)的編碼。哈夫曼編碼的實(shí)現(xiàn)方法如下：（1）利用字符集中每個(gè)字符的使用頻度作為權(quán)值構(gòu)造一個(gè)哈夫曼樹；（2）從根結(jié)點(diǎn)開始，與左孩子的連線標(biāo)上0，與右孩子的連線標(biāo)上1；（3）由根到某葉子結(jié)點(diǎn)的路經(jīng)上的0、1序列組成該葉子結(jié)點(diǎn)的編碼。例

假設(shè)有一個(gè)字符集包含8個(gè)字符：{a,b,c,d,e,f,g,h}，每個(gè)字符的使用頻度（權(quán)值）分別為{5,29,7,8,14,23,3,11}，為每個(gè)字符設(shè)計(jì)哈夫曼編碼。字符編碼a0001b10c1110d1111e110f01g0000h001哈夫曼編碼的實(shí)現(xiàn)算法首先根據(jù)字符的權(quán)值構(gòu)建哈夫曼樹，然后從每個(gè)葉子結(jié)點(diǎn)開始不斷的向上搜索雙親結(jié)點(diǎn)，直到根點(diǎn)為止，得出字符的哈夫曼編碼。編碼的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)算法的C函數(shù)描述如下：typedefstruct /*哈夫曼編碼的存儲(chǔ)結(jié)構(gòu)*/{charbits[N]; /*保存編碼的數(shù)組*/intstart; /*編碼的有效起始位置*/charch; /*字符*/}CodeType;CodeTypecode[N+1];/*字符編碼數(shù)組*/

huffmanCode(HufmTreetree[],CodeTypecode[]) /*利用哈夫曼樹求字符的哈夫曼編碼*/{inti,c,p;for(i=1;i<=N;i++)/*N次循環(huán)，分別得