《大学数据结构课件--第6章 树和二叉树综述》由会员分享，可在线阅读，更多相关《大学数据结构课件--第6章 树和二叉树综述（80页珍藏版）》请在金锄头文库上搜索。
1、1 F 6.1 树的定义和基本术语 F 6.2 二叉树 F 6.3 遍历二叉树和线索二叉树 F 6.4 树和森林 F 6.6 赫夫曼树及其应用 特点：非线性结构，一个直接前驱，但可能有多个 直接后继（1：n） 第6章 树和二叉树 2 1.树的定义 注：树的定义具有递归性，即树中还有树。 由一个或多个（n 0）结点组成的有限集合。在任何一棵非 空树T中： （1）有且仅有一个结点称为根（root）； （2）当n1时，其余的结点分为m（m 0）个 互不相交的有限集合T1、T2Tm。每个 集合本身又是棵树，被称作这个根的子树。 6.1 树的定义和基本术语 3 A 只有根结点的树 A BCD EFGHI
2、J KLM 根 子树 6.1 树的定义和基本术语 4 树的抽象数据类型定义 D是具有相同特性的数据元素的集合。 ADT ADT TreeTree TreeTree 数据对象D: 数据操作P: 数据关系R: 若D是空集，则称为空树；/允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： Root唯一/关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明 /至少15个 6.1 树的定义和基本术语 5 图形表示法 嵌套集合表示法 广义表表示法 凹入表示法（目录表示法） 树的表示方法 6.1 树的定义和基本术语 6 图形表示法： 大连工业大学 信息学院生物与
3、食品学院外语学院 数学物理电信计算机 根 子树 A BCD EFGH 6.1 树的定义和基本术语 7 广义表表示法： A BCD EFGH 根作为由子树森林组成的表的名字写在表的左边 A（B，C，D）A（B，C（E,F,G,H），D） 凹入表示法： A B C D E F G H 6.1 树的定义和基本术语 8 A BCD EFGH 嵌套表示法： A BD C E G F H 6.1 树的定义和基本术语 9 2.若干术语 A BCD JEFG HI KLM 根-根结点（没有前驱） 森林-指m棵不相交的树的集合 有序树-结点各子树从左至右有序，不能互换（左为第一） 无序树-结点各子树可互换位置
4、双亲-上层的那个结点（直接前驱） 孩子-下层结点的子树的根（直接后继） 兄弟-同一双亲下的同一层结点（孩子之间互称兄弟） 堂兄弟-双亲位于同一层的结点（但并非同一双亲） 祖先-从根到该结点所经分支的所有结点 子孙-该结点下层子树的任一结点 6.1 树的定义和基本术语 10 A BCD JEFG HI KLM 结点-树中的数据元素 结点的度-结点拥有的子树的数目（有几个直接后继度就是几） 结点的层次-从根到该结点的层数（根结点算第一层） 叶子-度为0的点（终端结点） 分支结点-度不为0的点（非终端结点） 树的度-所有结点度中的最大值（Max各结点的度） 树的深度-所有结点中最大的层数（ Max各
5、结点的层次 ） （或高度） 6.1 树的定义和基本术语 11 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转化为唯一对应的二叉树，不失一 般性。 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 6.2 二叉树 12 1 1、二叉树的定义、二叉树的定义 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。 基本特征：基本特征： 基本形态：基本形态： 具有3个结点的二叉树可能有几种不同形态？普通树呢？ 6.2 二叉树-定义 13 2 2、二叉树的性质、二叉树的性质 性质1：在二叉树的第i层上至多有2i-1个结点（i0）。 问：第i层上
6、至少有 个结点？ 性质2：深度为k的二叉树至多有2k-1个结点（k0）。 性质3：对于任何一棵二叉树，若度2的结点数有n2个， 叶子结点数为n0，则n0=n2+1。 6.2 二叉树-性质 14 证明性质3： 二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为2的结点数) 又 二叉树中全部结点数n=B+1(总分支数 + 根结点) （除根结点外，每个结点必有一个直接前驱，即一个分支） 而 总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继) 三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+1 6.2 二叉树-性质 15 满二叉树：深度为k且有 2
7、k-1个结点的二叉树。 特点：每一层上的结点数都是最大结点数。 可以对满二叉树的结点进行连续编号。 4 89 5 10 11 6 12 13 7 14 15 23 1 完全二叉树：深度为k，有n个结点的 二叉树，当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n 的结点一一 对应时，称之为完全二叉树。 特点: （1）叶子结点只可能在层次最大的两层上出现； （2）对任一结点，若其右分支下的子孙的最大层次为h， 则其左分支下的子孙的最大层次数必为h或h+1。 4 89 5 10 67 23 1 6.2 二叉树-特例 16 1 23 11 45 891213 67 101415 1 23 1
8、1 45 8912 67 10 1 23 45 67 1 23 456 6.2 二叉树-特例 17 对于特殊性质的二叉树，还具备以下2个性质： 性质4：具有n个结点的完全二叉树的深度必为 loglog 2 2 n n 1。 性质5：如果对一棵有n个结点的完全二叉树(其深度为 loglog 2 2 n n 1) 的结点按层序编号，则对任一结点i（1in），有： 1）如果i=1，则结点i是二叉树的根，无双亲；如果i1， 则其双亲parent（i）是结点 i/2 ； 2）如果2in，则结点i无左孩子(结点i为叶子结点)；否则其 左孩子lchild（i）是结点2i； 3）如果2i+1n，则结点i无右孩
9、子；否则其右孩子rchild(i) 是结点2i+1。 4 89 5 10 67 23 1 6.2 二叉树-性质 18 一、顺序存储结构 3 3、二叉树的存储结构、二叉树的存储结构 用一组地址连续的存储单元依次 自上而下、自左至右存储二叉树 上的结点元素。 D HI EFG BC A 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I D F E BC A 0 1 2 3 4 5 6 7 8 9 A B C D E 0 0 0 0 F 仅适合于完全二叉树 对于非完全二叉树： 将各层空缺处全部补上 “虚结点”，其内容为0 缺点：浪费空间；插入、删除不便 6.2 二叉树-存储
10、结构 19 二、链式存储结构 二叉链表中包含2个指针域。 一般从根结点开始存储。 DATA PARENT LCHILD RCHILD lchild data rchild lchild data parent rchild 为了便于找到结点的双亲， 可再增加一个双亲域指针， 将二叉链表变成三叉链表。 链表的头指针指向二叉树的根结点。 6.2 二叉树-存储结构 20 例： C EF D B G A A B CD EF G A B C D E F G 二叉链表 三叉链表 在含有n个结点的二叉链表中有n+1个空链域 空指针个数： 2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n
11、0+n1+n2+1 =n+1 6.2 二叉树-存储结构 21 一、遍历二叉树 按某条搜索路径访问树中每个结点，使得每个结点均被 访问一次，而且仅被访问一次。 v二叉树由根、左子树、右子树构成，三者的组合可构成6种 遍历方案：根左右、根右左、左根右、左右根、右根左、右左根 v若限定“先左后右”，则有3种实现方案： 根左右 左根右 左右根 先序遍历 中序遍历 后序遍历 6.3 遍历二叉树和线索二叉树 22 D HI FG BC A 1、 先序遍历 2、 中序遍历 3、 后序遍历 访问根结点 先序遍历左子树 先序遍历右子树 A BD CFGH I 中序遍历左子树 访问根结点 中序遍历右子树 DB A
12、 FCHGI 后序遍历左子树 后序遍历右子树 访问根结点 DB FHIGC A 例1： 6.3 遍历二叉树和线索二叉树 23 1、 先序遍历 2、 中序遍历 3、 后序遍历 +* / AB C DE A / B* C*D+E A B / C * D 例2： * AB /C *E + D *E+ 前缀表达式 中缀表达式 后缀表达式 6.3 遍历二叉树和线索二叉树 24 例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 讨论：若已知先序序列（或后序序列）和中序序列，能否恢复 出对应的二叉树？ 分析： 由后序遍历特征，根结点必在后序序列尾部（即A
13、） 由中序遍历特征，根结点必在其中间，而且其左部必全部是左 子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG） 继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子 串可确定F为A的右孩子；以此类推 6.3 遍历二叉树和线索二叉树 25 已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A （B D C E）（ F H G） A （D C E） BF G H C D E A A BC 6.3 遍历二叉树和线索二叉树 26 已知先序遍历序列如下：ABDCEF A BC E F D 6.3 遍历二叉树和线索二叉树 27 二、线索二叉树
14、 普通二叉树只能找到结点的左右孩子的信息，而该结点 的直接前驱和直接后继只能在遍历过程中获得。 若将遍历后对应的有关前驱和后继预存起来，则从第一 个结点开始就能很快地遍历整个树了。 例如中序遍历结果：A/B*C*D+E，实际上已将二叉树转为线 性排列，显然具有唯一前驱和唯一后继。 如何预存这类信息呢？ 增加两个域:前驱指针、后继指针 利用n+1个空链域 6.3 遍历二叉树和线索二叉树 28 规定： 1）若结点有左子树，则lchild指向其左孩子； 否则，lchild指向其直接前驱（即线索）； 2）若结点有右子树，则rchild指向其右孩子； 否则，rchild指向其直接后继（即线索）； lch
15、ild data rchild 约定： 当Tag域为0时，表示孩子情况； 当Tag域为1时，表示线索情况。 lchild LTag data RTag rchild 6.3 遍历二叉树和线索二叉树 29 有关线索二叉树的几个术语： 线索链表：用上述结点构成的二叉链表 线索：指向前驱和后继结点的指针 线索二叉树：同加上线索的二叉树（图形式样） 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程 线索化过程就是在遍历过程中修改空指针的过程： 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况”） 6.3 遍历二叉树和线索二叉树 30 例：画出下列二叉树所对应的中序线索二叉树 HH I I F F GG B B C C A A D D E E 中序遍历结果：HDIBE A FCG NIL NIL 6.3 遍历二叉树和线索二叉树 31 HH I I F F GG B B C C A A D D E E NIL NIL 0 1 0 A 0 0 B 0 0 C 0 0 D 0 1 E 1 1 F 1 1 G 1 1 H
