数据结构课件树和二叉树
1、第六章树和二叉树6.1树的定义和基本概念6.2二叉树6.2.1树的定义和基本术语6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换16.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树〔赫夫曼树〕6.6.2赫夫曼编码2v树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它特别类似于自然界中的树。树结构在客观世界里是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的
2、应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。36.1树的定义和基本术语v定义：树(Tree)是n(n=0)个结点的有限集T，T 为空时称为空树，否则它满足如下两个条件：〔1〕有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。4v树的基本概念：结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥
3、有的子树数叶子(leaf)——度为0的结点称为叶子或终端结点。非终端结点——度不为0的结点称为非终端结点或分支结点。5vv孩子(child)——结点子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。
双亲(parents)——若结点X有子女Y，则X为Y的双亲结点。兄弟(sibling)——同一个双亲的孩子之间互称兄弟。6v子孙结点——以某结点为根的子树中的任一结点都称为该结点的子孙。v结点的祖先是从根到该结点所经分支上的全部结点。v 树的度——一棵树中最大的结点度数v结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……7v深度(de
4、pth)——树中结点的最大层次数v森林(forest)——m(m?0)棵互不相交的树的集合v有序树——若一棵树中全部子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。v无序树——若一棵树中全部子树的次序无关紧要，则称为无序树。8ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先96.2二叉树v
5、二叉树在树结构的应用中起着特别重要的作用，因为对二叉树的很多操作算法简洁，而任何树都可以与二叉树互相转换，这样就解决了树的存储结构及其运算中存在的冗杂性。106.2.1二叉树的定义v定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。v这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。11v二叉树结点的子树要区分左子树和右子树。图6.8列出二叉树的5种基本形态，图6.8(C)和图6.8〔d〕是不同的两棵二叉树。(a)空二叉树AABABACB(b)根和
6、空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树图6.8二叉树的5种形式126.2.2二叉树的性质v二叉树具有以下重要性质：v性质1：在二叉树的第i层上至多有2i-1个结点(i=1)。v采纳归纳法证明此性质。v当i=1
时，只有一个根结点，2i-1=20=1，命题成立。v如今假定对全部的j，1=1).v深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，：?ki=1〔第i层上的最大结点数〕=?ki=12i-1=2k–114v性质3：对任何一棵二叉树，假如其终端结点数为n0，度为2的结点数为
n2，则n0
7、＝n2＋1。v设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中全部结点均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)v再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，v则有：N＝B＋1。15由于这些分支都是由度为1和2的结点射出的，全部有：B＝n1+2*n2N＝B＋1＝n1＋2n2＋1〔6－2)由式〔6－1〕和〔6－2〕得到：n0+n1+n2=n1+2*n2+1n0＝n2＋1两种特别形态的二叉树：满二叉树和完全二叉树。一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图6.9就是一棵满二叉树
8、，对结点进行了顺序编号16v假如深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。图6.9满二叉树245367117图6.10〔b
〕、〔c〕是2棵非完全二叉树。满二叉树是完全二叉树的特例。12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树图6.10完全二叉树18v完全二叉树的特点是：v 〔1)全部的叶结点都出如今第k层或k－1层。v〔2〕对任一结点，假如其右子树的最大层次为L，则其左子树的最大层次为L或L＋1。v性质4：具有n个结点的完全二叉树的深度为
9、[log2n]＋1。v符号【x】表示不大于x的最大整数。v假设此二叉树的深度为k，则依据性质2及完全二叉树的定义得到：2k-1－11，则其双亲PARENT(i)是结点?i/2?。v〔2〕假如2in，则结点i为叶子结点，无左孩子；否则，其左孩子LCHINA(i)是结点2i。v〔3〕假如2i＋1n，则结点i无右孩子；否则，其右孩子RCHINA(i)是结点2i＋1。20如图6.11所示为完全二叉树上结点及其左右子女在结点之间的关系。[i/2]ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1图6.11完全二叉树中结点i和i+1(a)
10、i和i+1结点在同一层(b)i和i+1结点不在同一层21v对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此时，结点i无孩子。结点i的右孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。v对于i1，可分为两种状况：v〔1〕设第j〔1n，则无左孩子。22v其右孩子必定为第j＋1层的第二个结点，编号为2i＋1。若2i+1n，则无右孩子。v〔2〕假设第j〔11时，假如i为左孩子，即2〔i/2)=i，则i/2是i的双亲；假如i为右孩子，i＝2p+1,i的双亲应为p，p＝〔i－1〕/2=[i/2].证毕246.2.3二叉树的存
11、储结构1.顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素。因此，必需把二叉树的全部结点支配成为一个恰当的序列，结点在这个序列中的互相位置能反映出结点之间的规律关系，用编号的方法：
#definemax-tree-size100typedeftelemtypesqbitree[max-tree-size];Sqbitr eebt；从树根起，自上层至下层，每层自左至右的给全部结点编号，其缺点是有可能对存储空间造成极大的浪费，在最坏的状况下，一个深度为H且只有H个结点的右单支树却需要2h-1个结点存储空间。而且，若常常需要插入与删除树中结点时，顺序存储方式
12、不是很好！25例如：4层共有24-1个结点v第i号结点的左右孩子肯定保存在第2i及2i+1号单元中。v缺点：对非完全二叉树而言，浪费存储空间结点编号123456789101112131415结点值12345000067000026v完全二叉树abcdefghijklABCDEFGHIJKL12345678910111227ABCDEFG表示该处没有元素存在仅仅为了好理解ABCDEFG一般二叉树282.二叉链表法v一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置v对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。lchild
13、Datarchild29v也可以在结点中加上指向父结点的指针域P。即三叉链表法v30例如用二叉链表法表示一棵树：A^BC^D^E^F^^G^^H^lchildDatarchild31二叉树的二叉链表存储表示
TypedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTN ode,*BiTree；有时也可用数组的下标来模拟指针，即开拓三个一维数组
Data,lchild,rchild分别存储结点的元素及其左，右指针域;32v基于该存储结构的二叉树基本操作有：vStatusCreateBiT
14、ree(BiTree//按先序次序输入二叉树中结点的值〔一个字符〕，空格字符表示空树，//构造二叉链表表示的二叉树T。
vStatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采纳二叉链表存储结构,Visit是对结点操作的应用函数//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次//一旦visit()失败，则操作失败
33vStatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采纳二叉链表存储结构,Visit是对结点
15、操作的应用函数//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次//一旦visit()失败，则操作失败
vStatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采纳二叉链表存储结构,Visit是对结点操作的应用函数//后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次v//一旦visit()失败，则操作
失败
34vStatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采纳二叉链表存储结构,Visit是
16、对结点操作的应用函数//层序遍历二叉树T，对每个结点调用函数Visit 一次且仅一次//一旦visit()失败，则操作失败35v建立一棵二叉树vStatusCreateBiTree(BiTreeif(ch==
＃)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLO W);36T-data=ch;//生成根结点CreateBiTree(T-lchild);//生成左子树CreateBiTree(T-rchild);//生成右子树}returnOK;}//CreateBiTree留意：
17、调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。376.3遍历二叉树和线索二叉树6.3.1遍历二叉树一、在二叉树的一些应用中，经常要求在树中查具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜寻路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。38假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD
18、六种遍历方案。若规定先左后右，则只有前三种状况，分别规定为：DLR——先〔根〕序遍历，LDR——中〔根〕序遍历，LRD——后〔根〕序遍历。1、
先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则〔1〕访问根结点；〔2〕先序遍历左子树；〔3〕先序遍历右子树。392、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则〔1〕中序遍历左子树；〔2〕访问根结点；〔3〕中序遍历右子树。3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则〔1〕后序遍历左子树；〔2〕后序遍历右子树；〔3〕访问根结点。40例如图〔1〕所示的二叉树表达式(a+b*(c-d)
19、-e/f)若先序遍历此二叉树，按访问结点的先后次序将结点排列起来，其先序序列为：-+a*b-cd/ef按中序遍历，其中序序列为：a+b*〔c-d〕-e/f按后序遍历，其后序序列为：abcd-*+ef/-人们喜爱中缀形式的算术表达式，对于计算机，使用后缀易于求值－＋/a*efb-cd图〔1〕41二、递归法遍历二叉树下面对于访问节点用printf替代，用二叉链表做为存储结构，三种遍历二叉树的递归算法描述先序遍历算法可描述为：voidPreOrder(BinTreeT){//算法里①~⑥是为了说明执行过程加入的标号①if(T){//假如二叉树非空②printf(
20、“％c”，T-data)；//访问根结点③PreOrder(T-lchild)；//访问左子树④PreOrder(T-rchild);//访问右子树⑤}⑥}//PreOrder42中序遍历算法可描述为：voidInOrder(BinTreeT){//算法里①~⑥是为了说明执行过程加入的标号①if(T){//假如二叉树非空②InOrder(T-lchild)；//访问左子树③printf(“％c”,T-data);//访问根结点④InOrder(T-rchild);//访问右子树
⑤}⑥}//InOrder43后序遍历算法可描述为：voidPosOrder(B
21、inTreeT){//算法里①~⑥是为了说明执行过程加入的标号①if(T){//假如二叉树非空②PosOrder(T-lchild)；//访问左子树③PosOrder(T-rchild);//访问右子树④printf(“％c”，T-data);//访问根结点⑤}⑥}//PosOrder44递归法遍历二叉树的通用算法v先序遍历二叉树递归算法：
Status(PreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采纳二叉链表存储结构，Visit是对数据元素操作的应用函数，//先序遍历二叉树T，对每个结点调用
22、函数Visit一次且仅一次。//一旦visit()失败，则操作失败。
if(T){if(Visit(T-data))45if(PreOrderTraverse(T-lchild,Visit))if(PreOr derTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//Pre OrderTraverse46v中序遍历的递归算法
vStatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(I nOrderTraverse(
23、T-lchild，Visit))if(Visit(T-data))if(InOrderTraverse(T-rchild，Visit))returnOK;returnERROR;}elsereturnOK;}//InOrderTraverse47v后序遍历的递归算法
vStatusPosOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if( PosOrderTraverse(T-lchild，Visit))if(PosOrderTraverse(T-rchild，Visit))if(Visit(T
二叉树的基本性质
24、-data))returnOK;returnERROR;}elsereturnOK;}//PosOrderTraverse48v 先序遍历结果：1,2,4,5,6,7,3v中序遍历结果：4,2,6,5,7,1,3v后序遍历结果：4,6,7,5,2,3,149三、非递归法遍历二叉树50三种遍历二叉树的非递归算法描述v中序遍历：
vStatusInorder(BiTreeT){BiTNode*p;p=T;InitStack(S);printf(“ninordert raversal:n);while(!(p==NULLp=p-lchild;}51Pop(S,p)
25、;//弹出栈顶元素处理printf(“%c”,p-data);p=p-rchild;//处理右子树}}}v解析：对于函数Inorder来说，在访问p所指的结点之前，若p所指结点的左链不空，则沿着其左链前进，在前进过程中，把历经的结点指针逐一送入栈中。这个过程始终重复到p为空，从而实现遍历左子树。然后，从栈中弹出一个结点的指针值，访问这个结点。接下来，p取其右链的值，实现遍历右子树。52先序遍历：
vStatusPreorder(BiTreeT){BiTNode*p;p=T;InitStack(S);printf(“npreorde rtraversal:n
26、);while(!(p==NULL//先处理根push(S,p);//根进栈，为了将来处理右子树p=p-lchild;//处理左子树}else{Pop(S,p);p=p-rchild;//处理右子树}}}53v解析：对于函数Preorder来说，在遍历过程中，访问完p所指的结点之后，把该结点的指针值送入栈中。然后，p取其左链的值；若不空，则在while 循环里连续遍历左子树；若p左链的值为空，但栈不空，则从栈中弹出一个结点的指针，于是,p返回到了它刚刚离开的结点，再取该结点右链的值，实现遍历右子树。整个遍历过程是在一个while循环里进行的。只有当p
为空，且
27、栈亦为空时，while循环方告结束。54v分析后序遍历过程：对于后序遍历，状况要冗杂一些。在访问一个结点之前，要两次历经这个结点。第一次，由该结点沿着其左链前进，遍历左子树。遍历完左子树之后，返回到这个结点。第二次，由该结点沿着其右链遍历右子树。遍历完右子树之后才能访问这个结点。这样，一个结点的指针值要两次进栈，两次出栈。只有在其第二次出栈之后，才能访问这个结点。为了记录结点指针从栈中弹出的次数，我们设置一个标志量sign，并且把sign的值和结点的指针一同送栈。55v这样，栈的数据结构为：v 栈的元素定义为typedefstruct{BiTNode*ptr
28、;intsign;}Selemtypev栈的结构定义：
vtypedefstruct{Selemtype*base;Selemtype*top;intstacksize;}Stack56v后序遍历：
vStatusPosorder(BiTreeT){BiTNode*p;Selemtypeselem;p=T;InitStack(S);pr intf(“nposordertraversal:n);do{if
〔p!=NULL){selem.ptr=p;selem.sign=1;push(S,selem);p=p-lchild;}elsewhi le(!StackEm
29、
pty(S)){57Pop(S,selem);p=selem.ptr;sign=selem.sign;if(sign==1){selem. ptr=p;selem.sign=2;push(S,selem);p=p-rchild;break;}elseif(sign==2){pr intf(“%c”,p-data);}}}while(!(p==t}586.3.2线索二叉树：当以二叉链表作为存储结构时，只能到结点的左右孩子的信息，而不能直接得到结点在任一序
列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到。如何保存这种在遍历过程中得到的信息呢？一个简洁的
30、方法是增加指针，这样做使得结构的存储密度大大降低。59另一方面，在有n个结点的二叉链表中必定存在n+1个空链域，能否利用这些空链域来存放结点的前驱和后继信息呢。答案是确定的。可以规定：若结点有左子树，则其lchild域存放其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域存放右孩子，否则令rchild域指示其后继。60为了能保存所需的信息，而避开混淆，需转变结点结构，可增加标志域；其中:0lchild域指示结点的左孩子ltag=1lchild域指示结点的前驱0rchild域指示结点的右孩子rtag=1rchild

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。