第六章西北大学树和二叉树.ppt
《第六章西北大学树和二叉树.ppt》由会员分享,可在线阅读,更多相关《第六章西北大学树和二叉树.ppt(133页珍藏版)》请在三一文库上搜索。
1、第6章 树和二叉树,6.1 树的定义与基本术语 6.2 二叉树 6.3 二叉树的遍历与线索化 6.4 树、森林和二叉树的关系 6.5 哈夫曼树及其应用 6.6 总结与提高,6.1 树的定义与基本术语,1树的基本概念 2树的图解表示法 3树的相关术语 4树的抽象数据类型,6.1 树的定义与基本术语,树定义:是n(n0)个结点的有限集合T。当n=0时,称为空树;当n0时,该集合满足如下条件:,(1) 其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。,(2) 其余n-1个结点可以划分成m(m0)个互不相交的有限集T1,T2,T3,Tm,其中Ti又是一棵树,称为根ro
2、ot的子树。每棵子树的根结点有且仅有一个直接前驱,可有零个或多个直接后继。,1树的基本概念,例如:一棵树的逻辑结构图(6.1)为:,从图中可以看出它好象一棵倒栽的树。,2树的图解表示法,1)倒置树结构(树形表示法)图6.1,2)文氏图表示法(嵌套集合形式) 图6.2,3)广义表形式(嵌套扩号表示法),4)凹入表示法 图6.3,图6.2 文氏图表示法,图6.3 凹入表示法,3.树的相关术语:,结点:包含一个数据元素及若干指向其它结点的分支信息。,结点的度:一个结点的子树个数称为此结点的度。,叶结点:度为0的结点,即无后继的结点,也称为终端结点。,分支结点:度不为0的结点,也称为非终端结点。,结点
3、的层次:从根结点开始定义,根结点的层次为1,根的直接后继的层次为2,依此类推。,结点的层次编号:将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列,依次给它们编以连续的自然数。,树的度:树中所有结点的度的最大值。,树的高度(深度):树中所有结点的层次的最大值。,有序树:在树T中,如果各子树Ti之间是有先后次序的,则称为有序树。,森林:m(m0)棵互不相交的树的集合。将一棵非空树的根结点删去,树就变成一个森林;反之,给森林增加一个统一的根结点,森林就变成一棵树。,同构:对两棵树,通过对结点适当地重命名,就可以使两棵树完全相等(结点对应相等,对应结点的相关关系也像等),则称这两棵树同构
4、。,双亲结点:一个结点的直接前驱称为该结点的双亲结点。上图中A是B、C的双亲。,兄弟结点:同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点H、I、J互为兄弟结点。,祖先结点:一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。如结点K的祖先结点是A、B、E。,子孙结点:一个结点的直接后继和间接后继称为该结点的子孙结点。如结点D的子孙是H、I、J、M。,孩子结点:一个结点的直接后继称为该结点的孩子结点。如上图的B、C是A的孩子。,我们常常借助人类家族树的术语,以便于直观理解结点间的层次关系。,堂兄弟:父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。在图6.1中,结点E、G、H互为堂兄弟。
5、,前辈:层号比该结点小的结点,都称为该结点的前辈。,后辈:层号比该结点大的结点,都称为该结点的后辈。,4.树的抽象数据类型,数据对象D:一个集合,该集合中的所有元素具有相同的特性。,数据关系R:若D为空集,则为空树。若D中仅含有一个数据元素,则R为空集,否则R=H,H是如下的二元关系:,(1) 在D中存在唯一的称为根的数据元素root,它在关系H下没有前驱。,(2) 除root以外,D中每个结点在关系H下都有且仅有一个前驱。,基本操作:,InitTree(Tree): 将Tree初始化为一棵空树。 (2) DestoryTree(Tree): 销毁树Tree。 (3) CreateTree(T
6、ree): 创建树Tree。 (4) TreeEmpty(Tree): 若Tree为空,则返回TRUE,否则返回FALSE。 (5) Root(Tree): 返回树Tree的根。 (6) Parent(Tree,x): 树Tree存在,x是Tree中的某个结点。若x为非根结点,则返回它的双亲,否则返回“空”。 (7) FirstChild(Tree,x): 树Tree存在,x是Tree中的某个结点。若x为非叶子结点,则返回它的第一个孩子结点,否则返回“空”。 (8) NextSibling(Tree,x): 树Tree存在,x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点,则返回x后
7、面的下一个兄弟结点,否则返回“空”。,基本操作:,(9) InsertChild(Tree,p,Child): 树Tree存在,p指向Tree中某个结点,非空树Child与Tree不相交。将Child插入Tree中,做p所指向结点的子树。 (10) DeleteChild(Tree,p,i): 树Tree存在,p指向Tree中某个结点,1id,d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。 (11) TraverseTree(Tree,Visit(): 树Tree存在,Visit()是对结点进行访问的函数。按照某种次序对树Tree的每个结点调用Visit()函数访问一次且最多一
8、次。若Visit()失败,则操作失败。,6.2 二叉树,6.2.1 二叉树的定义与基本操作,6.2.2 二叉树的性质,6.2.3 二叉树的存储结构,6.2.1 二叉树的定义与基本操作,定义:我们把满足以下两个条件的树型结构叫做二叉树(Binary Tree): (1)每个结点的度都不大于2; (2)每个结点的孩子结点次序不能任意颠倒。,下面给出二叉树的五种基本形态:,二叉树的基本操作:,Initiate(bt):将bt初始化为空二叉树。 (2) Create(bt):创建一棵非空二叉树bt。 (3) Destory(bt): 销毁二叉树bt。 (4) Empty(bt): 若bt为空,则返回T
9、RUE,否则返回FALSE。 (5) Root(bt): 求二叉树bt的根结点。若bt为空二叉树,则函数返回“空”。 (6) Parent(bt,x):求双亲函数。求二叉树bt中结点x的双亲结点。若结点x是二叉树的根结点或二叉树bt中无结点x,则返回“空”。,基本操作:,(7) LeftChild(bt,x):求左孩子。若结点x为叶子结点或x不在bt中,则返回“空”。 (8) RightChild(bt,x):求右孩子。若结点x为叶子结点或x不在bt中,则返回“空”。 (9) Traverse(bt): 遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。 (10) Clear(bt):
10、清除操作。将二叉树bt置为空树。,6.2.2 二叉树的性质,性质1:在二叉树的第i层上至多有2i-1个结点(i1)。,当i=1时,整个二叉树只有一根结点,此时2i-1=20=1,结论成立。,证明:,假设i=k时结论成立,即第k层上结点总数最多为2k-1个。,现证明当i=k+1时,结论成立:,因为二叉树中每个结点的度最大为2,则第k+1层的结点总数最多为第k层上结点最大数的2倍,即22k-1=2(k+1)-1,故结论成立。,性质2:深度为k的二叉树至多有2k-1个结点(k1)。,证明:,因为深度为k的二叉树,其结点总数的最大值是将二叉树每层上结点的最大值相加,所以深度为k的二叉树的结点总数至多为
11、:,故结论成立。,性质3:对任意一棵二叉树T,若终端结点数为n0,而其度数为2的结点数为n2,则n0= n2+1 。,证明:设二叉树中结点总数为n,n1为二叉树中度为1的结点总数。因为二叉树中所有结点的度小于等于2,所以有 n= n0+ n1+n2 设二叉树中分支数目为B,因为除根结点外,每个结点均对应一个进入它的分支,所以有:n=B+1。 又因为二叉树中的分支都是由度为1和度为2的结点发出,所以分支数目为: B=n1+2n2 整理上述两式可得到:n=B+1=n1+2n2+1 将n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1,整理后得n0= n2+1,故结论成立。,两
12、种特殊的二叉树:,满二叉树:深度为k且有2k-1个结点的二叉树。在满二叉树中,每层结点都是满的,即每层结点都具有最大结点数。,满二叉树,完全二叉树:,关系:满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。,深度为k,结点数为n的二叉树,如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应,则为完全二叉树,性质4:具有n个结点的完全二叉树的深度为2n+1。,证明:设n个结点的完全二叉树的深度为k,根据性质2可知,k-1层满二叉树的结点总数为: 2k-1-1 k层满二叉树的结点总数为: 2k-1 显然有: 2k-1 - 1 n 2k- 1 2k- 1 n 2k 取对数有:k -
13、1 log2n k 因为k是整数,所以k -1 =log2n , k= 2n+1 结论成立。,性质5:对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号,则对于任意的序号为i的结点有:,(1)若i = 1, 则 i 无双亲结点 若i 1, 则 i 的双亲结点为i /2 (2)若2*i n, 则 i 无左孩子 若2*in, 则 i 结点的左孩子结点为2*i (3)若 2*i+1 n ,则i 无右孩子 若 2*i+1n, 则i的右孩子结点为2* i+1,用归纳法证明其中的(2)和(3)。,6.2.3 二叉树的存储结构,二叉树的结构是非线性的,每一结点
14、最多可有两个后继。,二叉树的存储结构有两种:顺序存储结构和链式存储结构。,1.顺序存储结构:是用一组连续的存储单元来存放二叉树的数据元素 。,二叉树的顺序存储结构,对于一般的二叉树,我们必须按照完全二叉树的形式来存储,就会造成空间的浪费。单支树就是一个极端情况。,单支树,2. 链式存储结构,对于任意的二叉树来说,每个结点只有两个孩子,一个双亲结点。我们可以设计每个结点至少包括三个域:数据域、左孩子域和右孩子域:,二叉链表,二叉树T,二叉链表,typedef struct Node DataType data; strct Node * LChild; struct Node * RChild;
15、 BiTNode, *BiTree;,用C语言描述定义二叉树的二叉链表结构如下 :,结论:若一个二叉树含有n个结点,则它的二叉链表中必含有2n个指针域,其中必有n1个空的链域。,证明:,分支数目B=n-1,即非空的链域有n-1个,故空链域有2n-(n-1)=n+1个。,为了便于找到双亲结点,可以增加一个Parent域,以指向该结点的双亲结点。采用这种结点结构存放称做二叉树的三叉链表存储结构。,6.3 二叉树的遍历与线索化,6.3.1 二叉树的遍历 6.3.2 遍历算法应用 6.3.3 基于栈的递归消除 6.3.4 线索二叉树 6.3.5 由遍历序列确定二叉树,6.3 二叉树的遍历与线索化,二叉
16、树的遍历:指按一定规律对二叉树中的每个结点进行访问且仅访问一次。,二叉树的基本结构由根结点、左子树和右子树组成,如图示,6.3.1 二叉树的遍历,用L、D、R分别表示遍历左子树、访问根结点、遍历右子树,那么对二叉树的遍历顺序就可以有:,访问根,遍历左子树,遍历右子树(记做DLR)。 访问根,遍历右子树,遍历左子树(记做DRL)。 遍历左子树,访问根,遍历右子树(记做LDR)。 遍历左子树,遍历右子树,访问根 (记做LRD)。 遍历右子树,访问根,遍历左子树 (记做RDL)。 遍历右子树,遍历左子树,访问根 (记做RLD)。,在以上六种遍历方式中,如果我们规定按先左后右的顺序,那么就只剩有 DL
17、R 、LDR 和LRD三种。根据对根的访问先后顺序不同,分别称DLR为先序遍历或先根遍历;LDR为中序遍历(对称遍历);LRD为后序遍历。,注意:先序、中序、后序遍历是递归定义的,即在其子树中亦按上述规律进行遍历。,三种遍历方法的递归定义:,(1)先序遍历(DLR)操作过程:,若二叉树为空,则空操作,否则依次执行如下操作: 访问根结点; 按先序遍历左子树; 按先序遍历右子树。,若二叉树为空,则空操作,否则依次执行如下操作: 按中序遍历左子树; 访问根结点; 按中序遍历右子树。,(2)中序遍历(LDR)操作过程,(3)后序遍历(LRD)操作过程:,若二叉树为空,则空操作,否则依次执行如下操作:
18、按后序遍历左子树; 按后序遍历右子树; 访问根结点。,对于如下图的二叉树,其先序、中序、后序遍历的序列为: 先序遍历: A、B、D、F、G、C、E、H 。 中序遍历: B、F、D、G、A、C、E、H 。 后序遍历: F、G、D、B、H、E、C、A 。,以二叉链表作为存储结构,讨论二叉树的遍历算法,1) 先序遍历,void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ if (root!=NULL) Visit(root -data); /*访问根结点*/ PreOrder(root -LChild); /*先序遍历左子树*
19、/ PreOrder(root -RChild); /*先序遍历右子树*/ ,2) 中序遍历,void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ if (root!=NULL) InOrder(root -LChild); /*中序遍历左子树*/ Visit(root -data); /*访问根结点*/ InOrder(root -RChild); /*中序遍历右子树*/ ,3) 后序遍历,void PostOrder(BiTree root) /* 后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ i
20、f(root!=NULL) PostOrder(root -LChild); /*后序遍历左子树*/ PostOrder(root -RChild); /*后序遍历右子树* Visit(root -data); /*访问根结点*/ ,以中序遍历为例来说明中序遍历二叉树的递归过程,A,B,D,C,E,第一次经过,第二次经过,第三次经过,6.3.2 遍历算法应用,1.输出二叉树种的结点,【算法描述】 void PreOrder(BiTree root) /* 先序遍历输出二叉树结点, root为指向二叉树根结点的指针 */ if (root!=NULL) printf (root -data);
21、/* 输出根结点 */ PreOrder(root -LChild); /* 先序遍历左子树 */ PreOrder(root -RChild); /* 先序遍历右子树 */ ,【算法思想】输出二叉树中的结点并无次序要求,因此可用三种遍历算法中的任何一种完成,只需将访问操作具体变为打印操作即可。下面给出采用前序遍历实现的算法。,2.输出二叉树中的叶子结点,【算法思想】输出二叉树中的叶子结点与输出二叉树中的结点相比,它是一个有条件的输出问题,即在遍历过程中走到每一个结点时需进行测试,看是否满足叶子结点的条件。,【算法描述】 void PreOrder(BiTree root) /* 先序遍历输出
22、二叉树中的叶子结点 , root为指向二叉树根结点的指针 */ if (root!=NULL) if (root -LChild=NULL /* 先序遍历右子树 */ ,3.统计叶子结点数目,【算法思想】统计二叉树中的叶子结点数目并无次序要求,因此可用三种遍历算法中的任何一种完成,只需将访问操作具体变为判断是否为叶子结点及统计操作即可。,【算法描述】 /* LeafCount为保存叶子结点数目的全局变量,调用之前初始化值为0 */ void leaf(BiTree root) if(root!=NULL) leaf(root-LChild); leaf(root-RChild); if (ro
23、ot -LChild=NULL ,方法一:,【算法思想】采用递归算法,如果是空树,返回0;如果只有一个结点,返回1;否则为左右子树的叶子结点数之和。,【算法描述】 int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if (root-LChild=NULL) ,方法二:,3.统计叶子结点数目,4.建立二叉链表方式存储的二叉树,【算法思想】采用类似先序遍历的递归算法,首先读入当前根结点的数据,如果是.则将当前树根置为空,否则申请一个新结点,存入当前根结点的数据,分别用当前根结点的左子域和右子域进行递归调用,创
24、建左右子树。,【算法描述】 void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree( ,5.求二叉树的高度,设函数表示二叉树bt的高度,则递归定义如下: 若bt为空,则高度为0 若bt非空,其高度应为其左右子树高度的最大值加1,左 子 树,右 子 树,bt,hl,hr,High=max(hl+hr)+1,【算法思想】二叉树bt的高度可以递归定义如下: l 若bt为空,则高
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 西北大学 二叉
链接地址:https://www.31doc.com/p-2261746.html