数据结构（双语）15-16-BinaryTree

DataStructure

数据结构计算机与信息技术系袁莹2019年04月19日LogicalStructure（逻辑结构）Linear（list:stack/queue）StorageStructure（存储结构）sequential&linkedOperate（运算）InsertDeleteFindReviewReview线性表(LinearList)分类存储结构普通线性表(List)特殊线性表栈(Stack)队列(Queue)顺序结构(Sequential)(数组实现)顺序表顺序栈顺序队列（循环队列）链式结构(Linked)(指针实现)链表链栈链队（单循环链表）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的节点数为2个，度为2的节点数为1个，度为1的节点数为2个，则度为0的节点数为（）。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下标结点ABDCE#####F01234567891011下标结点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个节点的完全二叉树的深度为（⌊log2N⌋）？4.2.1ImplementationCompleteBinaryTree（1）若结点i有父亲（即i>1），则父亲的序号为⌊i/2⌋。（2）若结点i有左孩子（即2i<=n时），则左孩子为2i。（3）若结点i有右孩子（即2i+1<=n时），则右孩子为2i+1。（4）当i为偶数且i≠n时，它有右兄弟，右兄弟为i+1。（5）当i为奇数且i≠1时，它有左兄弟，左兄弟为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) /*当二叉树非空，进入递归过程；

否则，遍历运算结束*/{

printf("%c",T->Element); /*访问根结点*/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); /*访问根结点*/}}Algorithm3：InorderTraversalvoidInOrder(BiTree*T) /*中序遍历二叉树*/{ if(T){InOrder(T->Left); /*中序遍历左子树*/printf("%c",T->Element); /*访问根结点*/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二、选择题三、填空题四、简答题3（1）*Huffmantree一、哈夫曼树的定义及建立

结点的路径长度（lengthofpath）就是从根结点到每个结点的路径长度，其值为路经上的边数。赋予了权值的结点的路径长度与该结点权值的乘积即为结点的带权路径长度（WeightedPathLengthofNode）。树的带权路径长度（WeightedPathLengthofTree，缩写为WPL）定义为：树中所有叶子结点的带权路径长度之和，记为：其中n表示叶子结点数，wi表示第i个叶子结点的权值，li代表第i个叶子结点的路径长度。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）又称最优二叉树，是在含有n个叶子结点，权值分别为w1，w2，……，wn的所有二叉树中，带权路径长度WPL最小的二叉树。哈夫曼（D.A.Huffman）在上世纪五十年代初便提出了一个非常简单的算法来建立哈夫曼树，其算法描述如下：（1）将给定的n个权值{w1，w2，...，wn}作为n个根结点的权值，构造一个具有n棵二叉树的森林{T1，T2，...，Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根点权值最小的二叉树分别作为左、右子树，增加一个新结点作为根，从而将两棵树合并成一棵树，新根结点的权值为左右子树根结点权值之和。森林中因此也减少了一棵树；（3）重复上面步骤（2）的处理过程，直到森林中只有一棵二叉树为止，这棵二叉树就是哈夫曼树。Huffmantree从哈夫曼树构造过程和生成结果可知，哈夫曼树具有以下特点：（1）哈夫曼树不唯一。（2）哈夫曼树中只包含度为0和度为2的结点。（3）树中权值越大的叶子结点离根结点越近。例

假设树中叶子结点的权值为{5,29,7,8,14,23,3,11}，构造一棵哈夫曼树。（1）将给定的8个权值作为根结点，构造具有8棵树的森林（2）从森林中选取根点权值最小的两棵二叉树3、5，分别作为左右子树，构造一棵新的二叉树，新树根点权值为8，森林中减少一棵树。（3）重复步骤（2），直到森林中只剩一棵二叉树为止。Huffmantree方便查找父亲，将哈夫曼树的存储结构设计为三叉链表。每个结点包含四个域：weight为结点的权值，lchild、rchild、parent分别为左、右孩子和父亲结点的指针。含有N个叶子结点的哈夫曼树共有2N-1个结点，由此可定义一个长度为2N-1的数组tree来存储哈夫曼树，下标从1开始，0代表指针空（NULL）。weightparentlchildrchildtypedefstruct /*哈夫曼树结点的存储结构*/{ floatweight; /*结点的权值*/ intparent; /*双亲在数组中的下标*/ intlchild,rchild;/*左右孩子在数组中的下标*/}HufmTree;HufmTreetree[2N];在上述存储结构上实现哈夫曼算法的过程如下：（1）将哈夫曼树数组tree中的2N-1个结点初始化：即将各结点的权值、双亲、左孩子、右孩子均置为0。（2）读入N个叶子结点的权值，分别存入数组tree[i]（1≤i≤N）的权值域中，构造包含N棵树的初始森林，森林中的每棵树只有一个根结点。（3）循环N-1次，对森林中的树进行N-1次合并，产生N-1个新结点，依次放入数组tree[i]中（N+1≤i≤2N-1）。每次合并的步骤是：1）在当前森林的所有结点tree[j]（1≤j≤i-1）中，选取具有最小权值和次小权值的两个根结点（parent域为0的结点），分别用p1和p2记住这两个根结点在数组tree中的下标。2）将根为tree[p1]和tree[p2]的两棵树合并，使其成为新结点tree[i]的左、右孩子，得到一棵以新结点tree[i]为根的二叉树即将tree[i].weight赋值为tree[p1].weight和tree[p2].weight之和tree[i]的左指针赋值为p1；tree[i]的右指针赋值为p2；同时将tree[p1]和tree[p2]的双亲域均赋值为i，使其指向新结点tree[i]即它们在当前森林中已不再是根结点。

以（2,3,6,8）为例，分析哈夫曼树构造的实现算法数组下标weightparentlchildrchild012000230003600048000500006000070000二、哈夫曼编码及译码在进行文字传输时，数据通信的发送方需要将原文中的每一个文字转换成对应的二进制0、1序列（编码）进行发送，接收方接收到二进制的0、1串后再还原成原文（译码）。其编码和译码的过程如下所示：原文

电文（二进制的0、1序列）

原文常用的编码方式有两种：等长编码和不等长编码。等长编码：ASCⅡ码，其特点是每个字符的编码长度相同。编码简单且具有唯一性，当字符集中的字符在电文中出现的频度相等时，它是最优的编码。不等长编码：字符的编码长度不等，因此称这种编码方式为不等长编码。为了使译码唯一，则要求字符集中任一字符的编码都不是其他字符编码的前面一部分，这种编码叫做前缀（编）码。二、哈夫曼编码及译码利用二叉树来对叶子结点进行编码，所得的编码一定为前缀码。若要使报文总长最短，则利用哈夫曼树对叶子结点进行编码一定是最优的编码。哈夫曼编码的实现方法如下：（1）利用字符集中每个字符的使用频度作为权值构造一个哈夫曼树；（2）从根结点开始，与左孩子的连线标上0，与右孩子的连线标上1；（3）由根到某叶子结点的路经上的0、1序列组成该叶子结点的编码。例

假设有一个字符集包含8个字符：{a,b,c,d,e,f,g,h}，每个字符的使用频度（权值）分别为{5,29,7,8,14,23,3,11}，为每个字符设计哈夫曼编码。字符编码a0001b10c1110d1111e110f01g0000h001哈夫曼编码的实现算法首先根据字符的权值构建哈夫曼树，然后从每个叶子结点开始不断的向上搜索双亲结点，直到根点为止，得出字符的哈夫曼编码。编码的存储结构及实现算法的C函数描述如下：typedefstruct /*哈夫曼编码的存储结构*/{charbits[N]; /*保存编码的数组*/intstart; /*编码的有效起始位置*/charch; /*字符*/}CodeType;CodeTypecode[N+1];/*字符编码数组*/

huffmanCode(HufmTreetree[],CodeTypecode[]) /*利用哈夫曼树求字符的哈夫曼编码*/{inti,c,p;for(i=1;i<=N;i++)/*N次循环，分别得