《数据结构与算法 第3版 教学课件 ppt 作者 张小莉 第4章 树结构》由会员分享，可在线阅读，更多相关《数据结构与算法 第3版 教学课件 ppt 作者 张小莉 第4章 树结构（98页珍藏版）》请在金锄头文库上搜索。
1、第4章 树结构,2019年5月25日,1教学内容 二叉树和树的概念、二叉树的遍历及其应用、线索二叉树、哈夫曼树及哈夫曼编码、树和森林与二叉树之间的转换、树或森林的遍历。 教学目的 深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；掌握二叉树的三种遍历算法；了解二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题; 掌握森林与二叉树间的相互转换；掌握树和森林的遍历方法。,2019年5月25日,教学重点： 二叉树的定义、逻辑特点及性质；二叉树的存储结构；二叉树的遍历方法及其算法；以遍历为基础在二叉树上实现的几种运算；哈夫曼树和哈夫曼算法；树的存
2、储结构；森林与二叉树的转换。 教学难点： 二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的算法；二叉树上的复杂运算；哈夫曼算法及其应用；,2019年5月25日,4.1 引言,4.1.1 问题提出 问题1：组织结构层次关系的存储与查找。 问题2：家族族谱中家族成员之间的关系表示与查找。 问题3：图书馆中图书的分类关系的建立。 。,2019年5月25日,1树的定义,树（Tree）是n（n0）个有限数据元素的集合。当n0时，称这棵树为空树。在一棵非空树T中： (1) 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 (2) 若n1，除根结点之外的其余数据元素被分成m（m0）个互不相
3、交的集合T1, T2, , Tm，其中每一个集合Ti（1im）本身又是一棵树。树T1, T2, , Tm称为这个根结点的子树。,4.1.2 相关概念,2019年5月25日,2019年5月25日,树具有下面两个特点： 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 树中所有结点可以有零个或多个后继结点。 由此特点可知，下图所示的都不是树结构。,2019年5月25日,3相关术语 (1) 结点的度 (2) 叶结点 (3) 分支结点 (4) 左孩子、右孩子、双亲、兄弟,(5) 路径、路径长度 (6) 祖先、子孙 (7) 结点的层数 (8) 树的深度,2019年5月25日,（9）树
4、的度 （10）有序树和无序树 （11）森林,2019年5月25日,1二叉树的定义,4.2.1 二叉树的概念,4.2 二叉树,2019年5月25日,2二叉树的相关术语 (1) 满二叉树。,2019年5月25日,(2) 完全二叉树。,2019年5月25日,3.二叉树的基本操作 (1) Initiate(bt) (2) Create(x, lbt, rbt) (3) InsertL(bt, x, parent) (4) InsertR(bt, x, parent) (5) DeleteL(bt, parent) (6) DeleteR(bt, parent) (7) Search(bt, x) (8
5、) Traverse(bt),2019年5月25日,4.2.2 二叉树的主要性质,性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i1）。 性质2 一棵深度为k的二叉树中，最多具有2k1个结点。 性质3 对于一棵非空的二叉树，若叶子结点数为n0，度数为2的结点数为n2，则有：n0n21。 性质4 具有n个结点的完全二叉树的深度k为： log2n+1,2019年5月25日,性质5: 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有： 如果i1，则序号为i的结点的双亲结点的序号为i/2；如果i1，则序号为i的结
6、点是根结点，无双亲结点。 如果2in，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。 如果2i1n，则序号为i的结点的右孩子结点的序号为2i1；如果2i1n，则序号为i的结点无右孩子。 此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i1)/2，左孩子的编号为2i1，右孩子的编号为2i2。,2019年5月25日,4.2.3 二叉树的存储,1顺序存储结构 所谓二叉树的顺序存储，是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。,2019年5月25日,下面给出一棵完全二叉树的顺序存储示意。,201
7、9年5月25日,对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,2019年5月25日,极端情况是单支树，如一棵深度为k的右单支树，只有k个结点，却需分配2k1个存储单元。,显然，对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。,2019年5月25日,二叉树的顺序存储结构可描述为： #define MAXNODE 1024 /二叉树的最大结点数，可根据
8、实际情况进行修改 typedef datatype SqBiTreeMAXNODE; /0号单元存放根结点 定义一个顺序存储的二叉树变量：SqBiTree bt; 即将bt为含有MAXNODE个datatype类型元素的一维数组。,2019年5月25日,2链式存储结构 (1)二叉链表存储,2019年5月25日,下图(a)给出一棵二叉树的二叉链表存储表示。二叉链表也可以带头结点的方式存放，如图(b)所示。,2019年5月25日,二叉树的二叉链表存储结构可描述为： typedef struct bitnode datatype data; struct bitnode *lchild;*rchil
9、d; /左右孩子指针 BiTNode, *BiTree; 定义一个指向二叉树的指针变量：BiTree t;,2019年5月25日,(2)三叉链表存储 每个结点由四个域组成，具体结构为：,2019年5月25日,下图给出一棵二叉树的三叉链表存储示意图。,2019年5月25日,4.2.4 二叉树基本运算的实现,算法的实现依赖于具体的存储结构，当二叉树采用不同的存储结构时，上述各种操作的实现算法是不同的。 下面讨论基于二叉链表存储结构的上述操作的实现算法。,2019年5月25日,(1) Initiate(bt)：建立一棵空的二叉树bt，并返回bt。,2019年5月25日,(2) Create(x，lb
10、t，rbt)：生成一棵以x为根结点的数据域值以lbt和rbt为左右子树的二叉树。,2019年5月25日,(3) InsertL(bt, x, parent)：在二叉树bt中的parent所指结点和其左子树之间插入数据元素为x的结点,(4) InsertR(bt，x，parent)：功能类同于(3) ，算法略。,2019年5月25日,(5)DeleteL(bt，parent)：在二叉树bt中删除parent的左子树,(6) DeleteR(bt，parent)：算法略。,2019年5月25日,4.3 二叉树的遍历,二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问
11、一次。二叉树遍历是二叉树中最重要最基本的运算。,2019年5月25日,4.3.1 递归方法实现二叉树的三种遍历,若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树， 如果限定先左后右，则有三种方式，即： DLR（称为先序遍历) LDR（称为中序遍历) LRD（称为后序遍历) 。,2019年5月25日,1先序遍历 先序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1) 访问根结点； (2) 先序遍历根结点的左子树； (3) 先序遍历根结点的右子树。,2019年5月25日,对于上图所示的二叉树，按先序遍历所得到的结点序列为： A B D G C E F,2019年5月2
12、5日,2中序遍历 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1) 中序遍历根结点的左子树； (2) 访问根结点； (3) 中序遍历根结点的右子树。,2019年5月25日,对于上图所示的二叉树，按中序遍历所得到的结点序列为： D G B A E C F,2019年5月25日,3后序遍历 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1) 后序遍历根结点的左子树； (2) 后序遍历根结点的右子树； (3) 访问根结点。,2019年5月25日,对于上图所示的二叉树，按后序遍历所得到的结点序列为： G D B E F C A,2019年5月25日,4.3.2 非递归方法实现二叉
13、树的三种遍历,1、包络线 下图中所示的从根结点左外侧开始，由根结点右外侧结束的曲线，称其为该二叉树的包络线，二叉树的遍历是沿着该线路进行的。沿着该路线按标记的结点读得的序列为先序序列，按*标记读得的序列为中序序列，按标记读得的序列为后序序列。,2019年5月25日,2、栈的使用 先序遍历是沿着包络线深入时遇到结点就访问；中序遍历是在从左子树返回时遇到结点访问；后序遍历是在从右子树返回时遇到结点访问。,2019年5月25日,3、遍历算法 (1)先序遍历的非递归实现,2019年5月25日,(2)中序遍历的非递归实现 中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的Visit(p-data
14、)移到p=stacktop和p=p-rchild之间即可。,2019年5月25日,(3)后序遍历的非递归实现 特点：每一个结点两次入栈两次出栈。,2019年5月25日,2019年5月25日,4.3.3 按层次遍历二叉树 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于下图所示的二叉树，按层次遍历所得到的结果序列为： A B C D E F G,2019年5月25日,1、队列的使用 在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个
15、操作： 访问该元素所指结点； 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。,2019年5月25日,2019年5月25日,4.4 二叉树遍历的应用,4.4.1 构造二叉树的二叉链表存储 构建一棵二叉树的二叉链表也是基于遍历的过程进行的。这里按照先序遍历的过程构建。 首先建立二叉树带空指针的先序次序，依此作为构建时结点的输入顺序，如对于下图所示的二叉树，输入序列为：ABD0G000CE00F00（0表示空，为了简化问题，设数据元素的类型为字符型）。,2019年5月25日,2019年5月25日,4.4
16、.2 在二叉树中查找值为x的数据元素,2019年5月25日,4.4.3 统计给定二叉树中叶子结点的数目,2019年5月25日,4.4.4 由遍历序列恢复二叉树,从前面讨论的二叉树的遍历知道，任意一棵二叉树结点的先序序列和中序序列都是唯一的。 反过来，若已知结点的先序序列和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？,2019年5月25日,2、分隔过程： 已知一棵二叉树的先序序列与中序序列分别为： A B C D E F G H I ， B C A E D G H F I，试恢复该二叉树。,1、依据遍历定义： 由二叉树的先序序列和中序序列可唯一地确定该二叉树。 由二叉树的后序序列和中序序列也可唯一地确定该二叉树。 由二叉树的先序序列和后序序列不能唯一地确定该二叉树。,2019年5月25日,2019年5月25日,4.5 线索二叉树,4.5.1 线索二叉树的定义及结构 1线索二叉树的定义 利用二叉链表中左、右空指
