《数据结构-数和二叉树》由会员分享,可在线阅读,更多相关《数据结构-数和二叉树(72页珍藏版)》请在金锄头文库上搜索。
1、第 1 页第 2 页第六章 树和二叉树第六章 树和二叉树6.1 树的有关概念6.2 二叉树6.3 二叉树的遍历6.4 遍历的应用6.6 树和森林6.7 哈夫曼树及应用第 3 页第六章 树和二叉树6.1 树的有关概念1. 树的概念2. 树的应用3. 树的表示4.树的有关术语5 树的基本操作第 4 页6.1 树的有关概念1树的概念 树形结构是一种重要的非线性结构,讨论的是层次和分支关系。 树是n个结点的有限集合,在任一棵非空树中: (1)有且仅有一个称为根的结点。 (2)其余结点可分为个互不相交的集合,而且这些集合中的每一 集合都本身又是一棵树,称为根的子树。树是递归结构,在树的定义中又用到了树的
2、概念JIACBDHGFEKLM第 5 页6.1 树的有关概念例:下面的图是一棵树T=A, B, C, D, E, F, G, H, I, J,K,L,MA是根,其余结点可以划分为3个互不相交的集合:T1=B, E, F,K,L , T2=C, G , T3=D, H, I, J,M这些集合中的每一集合都本身又是一棵树,它们是A的子树。例如 对于 T11,B是根,其余结点可以划分为2个互不相交的集合:T11=E,K,L,T12=F,T11,T12 是B 的子树。JIACBDHGFEKLM第 6 页6.1 树的有关概念从逻辑结构看: 1)树中只有根结点没有前趋; 2)除根外,其余结点都有且仅一个前
3、趋;3)树的结点,可以有零个或多个后继; 4)除根外的其他结点,都存在唯一条从根到该结点的路径;5)树是一种分支结构 (除了一个称为根的结点外)每个元素都有且仅有一个直接前趋,有且仅有零个或多个直接后继。JIACBDHGFEKLM第 7 页6.1 树的有关概念2树的应用 1)树可表示具有分支结构关系的对象 例1家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J,K,L,M他们之间的关系可下图所示的树表示:例2单位行政机构的组织关系JIACBDHGFEKLM第 8 页6.1 树的有关概念2)树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系,但是为了便于管理和使用
4、数据,将它们用树的形式来组织。例3 计算机的文件系统不论是DOS文件系统还是window文件系统,所有的文件是用树的形式来组织的。文件夹1 文件夹n 文件1 文件2文件夹11 文件夹12 文件11 文件12C第 9 页6.1 树的有关概念3 树的表示 1)图示表示 2)二元组表示 3)嵌套集合表示 4)凹入表示法(类似书的目录) 5)广义表表示 AED HJIKLMDGCABEKLF CG D HMJI第 10 页6.1 树的有关概念4树的 基本术语树的结点:包含一个数据元素及若干指向子树的分支; 孩子结点:结点的子树的根称为该结点的孩子; 双亲结点:B 结点是A 结点的孩子,则A结点是B 结
5、点的双亲; 兄弟结点:同一双亲的孩子结点; 堂兄结点:同一层上结点; 祖先结点: 从根到该结点的所经分支上的所有结点子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙JIACBDHGFEKLM第 11 页6.1 树的有关概念4树的 基本术语结点层:根结点的层定义为1;根的孩子为第二层结点,依此类推; 树的深度:树中最大的结点层 结点的度:结点子树的个数 树的度: 树中最大的结点度。 叶子结点:也叫终端结点,是度为 0 的结点; 分枝结点:度不为0的结点;有序树:子树有序的树,如:家族树; 无序树:不考虑子树的顺序;森林;互不相交的树集合;森林和树之间的联系是:一棵树去掉根,其子树构成一个
6、森林;一个森林增加一个根结点成为树。JIACBDHGFEKLM第 12 页6.1 树的有关概念5 树的基本操作树的应用很广,应用不同基本操作也不同。下面列举了树的一些基本操作: 1)initiate (T); T 树的初始化,包括建树。2) root (T); 求T 树的根。3)parent (T , x ): 求T 树中 x 结点的双亲结点。4)Child (T, x, i ): 求 T 树中 x 结点的第 i 个孩子结点。5)right_sibling (T, x ): 求T 树中 x 结点的右兄弟 6)insert_Child (y, i, x ): 将根为 x 的子树置为 y 结点的第
7、 i 个孩子7) del_child (x, i); 删除 x 结点的第i 个孩子 8)traverse (T); 遍历T树。按某个次序依次访问树中每一个结点,并使每个结点都 被访问且只被访问一次。9)clear (T); 置空T 树第 13 页6 2 二 叉 树树是一种分支结构的对象,在树的概念中, 对每一个结点孩子的个数没有限制,因此树的 形态多种多样,本章我们主要讨论一种最简单 的树二叉树。第 14 页第六章 树和二叉树6.2 二叉树一 二叉树的概念二 二叉树的性质三 二叉树的存储结构第 15 页6.2 二 叉 树一 二叉树的概念1 二叉树的定义二叉树: 或为空树,或由根及两棵不相交的左
8、子树、右子树构成,并且 左、右子树本身也是二叉树。说明 1)二叉树中每个结点最多有两棵子树;二叉树每个结点度小于等于2; 2)左、右子树不能颠倒有序树; 3)二叉树是递归结构,在二叉树的定义中又用到了二叉树的概念;AFGE DCB第 16 页6.2 二 叉 树AFGE DCB(a)、(b)是不同的二叉树, (a)的左子树有四个结点,(b)的左子树有两个结点,(a)AGE DB CF(b)第 17 页6.2 二 叉 树2 二叉树的基本形态(a)空树(b)仅有根(c) 右子树空(e) 左子树空(d) 左、右子树均在第 18 页6.2 二 叉 树3应用举例 例1 可以用二叉树表示表达式a+b*(c-
9、d)-e/fedcbfa+*/-第 19 页6.2 二 叉 树例2 双人比赛的所有可能的结局 甲 乙甲 乙 甲 乙甲 乙 甲 乙甲 乙 甲 乙 甲 乙 甲 乙甲 乙甲 乙 甲 乙甲 乙开始开局连赢两局 或五局三胜第 20 页6.2 二 叉 树二 二叉树性质 性质1 在二叉树的第i 层上最多有2i-1个结点 性质2 深度为k的二叉树最多有 2k-1 个结点 性质3 设二叉树叶子结点数为n0,度为2的结点n2,则n0 = n2 +1AFGE DCB第 21 页6.2 二 叉 树两种特殊的二叉树满二叉树:如果深度为k的二叉树,有2k-1个结点则称为满二叉树;AG F E DCBAC BK=3的满二叉
10、树K=2的满二叉树第 22 页6.2 二 叉 树完全二叉树:如果一颗二叉树只有最下一层结点数可能未达到最大 ,并且最下层结点都集中在该层的最左端,则称为完全二叉树;AE DCBGAE DCB(a)(c)(b)(a)、(b)完全二叉树(c) 不是完全二叉树AG F E DCB第 23 页6.2 二 叉 树下面是两个关于完全二叉树的性质 性质4 具有n个结点的完全二叉树的深度为:trunc(log2 n)+1. trunc(x) 为取整函数。对完全二叉树的结点编号:从上到下,每一层从左到右AF E DCB123456性质5:在完全二叉树中编号为i的结点 1)若有左孩子,则左孩编号为2i 2)若有右
11、孩子,则右孩子结点编号为2i+1 3)若有双亲,则双亲结点编号为trunc(i/2)第 24 页6.2 二 叉 树三二叉树存贮结构1 二叉树的顺序结构满二叉树或完全二叉树的顺序结构用一组连续的内存单元,按编号顺序依次存储完全二叉树的元素.例如,用一维数组bt 存放一棵完全二叉树,将标号为 i 的结点的数据元素存放在分量 bti中。存储位置隐含了树 中的关系,树中的关系是通过完全二叉树的性质实现的。例如, bt6的双亲结点标号是k=trunc(i/2)=3,双亲结点所对应的数组分 量btk顺序结构图示0 1 2 3 4 5 6 7 m-1A B C D E FAF E DCB123456第 25
12、 页6.2 二 叉 树非完全二叉树的顺序结构按完全二叉树的形式补齐二叉树所缺少的那些结点,对二叉树结点编号, 将二叉树原有的结点按编号存储到内存单元“相应”的位置上。但这种方式对 于畸形二叉树,浪费较大空间。AFGE DCB1672453810AFGE DCB90 1 2 3 4 5 6 7 8 9 10 m-1A B C D E 0 F 0 0 G第 26 页6.2 二 叉 树2 二叉链表二叉链表中每个结点包含三个域:数据域、左指针域、右指针 域 AFEDCBStruct node int data;struct node *lch,*rch; ;二叉链表图示 DAB C E F 第 27
13、页6.2 二 叉 树AFEDCB3 三叉链表三叉链表中每个结点包含四个域:数据域、双亲指针域、左指针域、 右指针域Struct node int data;struct node *lch,*rch,*parent;ABDFEC第 28 页6.3 二叉树的遍历一. 二叉树的遍历方法二. 遍历的递归算法三. 遍历的非递归算法第 29 页6.3 二叉树的遍历遍历:按某种搜索路径访问二叉树的每个结点,而且每个结点仅被访 问一次。 访问:含义很广,可以是对结点的各种处理,如修改结点数据、输出 结点数据。遍历是各种数据结构最基本的操作,许多其他的操作可以在遍历 基础上实现。 如何访问二叉树的每个结点,而
14、且每个结点仅被访问一次?第 30 页6.3 二叉树的遍历一二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为:访问根,遍历左子树和遍历右子树令:L:遍历左子树T:访问根结点R:遍历右子树有六种遍历方法:T L R,L T R,L R T,T R L,R T L,R L T约定先左后右,有三种遍历方法: T L R、L T R、L R T ,分别称 为 先序遍历、中序遍历、后序遍历AFGE DCB第 31 页6.3 二叉树的遍历先序遍历(T L R)若二叉树非空(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树;先序遍历序列:A,B,D,E,G,C,FAFGE
15、DCB例:先序遍历右图所示的二叉树(1)访问根结点A(2)先序遍历左子树:即按 T L R 的顺序遍历左子树(3)先序遍历右子树:即按 T L R 的顺序遍历右子树第 32 页6.3 二叉树的遍历中序遍历(L T R) 若二叉树非空 (1)中序遍历左子树 (2)访问根结点 (3)中序遍历右子树中序遍历序列: D,B,G,E,A,C,FAFGE DCB例:中序遍历右图所示的二叉树(1)中序遍历左子树:即按 L T R 的顺序遍历左子树(2)访问根结点A(3)中序遍历右子树:即按 L T R 的顺序遍历右子树第 33 页6.3 二叉树的遍历后序遍历(L R T) 若二叉树非空 (1)后序遍历左子树 (2)后序遍历右子树 (3)访问根结点后序遍历序列: D,G,E,B,F,C,A例:后序遍历右图所示的二叉树(1)后序遍历左子树:即按 L R T 的顺序遍历左子树(2)后序遍历右子树:即按 L R T 的顺序遍历右子树(3)访问根结点AAFGE DCB第 34 页6.3 二叉树的遍历edcbfa+*/-