数据结构(java)树与二叉树.ppt

,基本内容,第6章树与二叉树,1.树的定义 树（tree）是由n(n0)个有限数据元素组成的数据集合，其中数据元素被称为结点。同时，树还必须满足以下两个条件： 在树中有一个特殊的结点被称为根结点，它只有后继结点，没有前驱结点。 除根结点以外，其余结点可以分为m（m0）个互不相交的集合T1，T2，Tm，其中每一个集合Ti（1im）本身又是一棵树。树T1，T2，Tm称为根结点的子树。,一.树的定义和基本术语,1.树的定义,一.树的定义和基本术语,2. 基本术语 1）双亲结点、子结点、兄弟结点 如图6.2中，B结点为E结点的双亲结点；A结点为D结点的双亲结点；D结点为I结点的双亲结点 如图6.2中，E结点为B结点的子结点；D结点为A结点的子结点；H结点为D结点的子结点 如图6.2中，B结点和C、D结点互为兄弟结点；结点G和H不为兄弟结点。 2）叶子结点 没有后继的结点称为叶子结点，如图6.2中的E、F、G、H、I结点。,一.树的定义和基本术语,2. 基本术语 3）结点的度 结点的度是结点所拥有的子树的棵数。如图6.2中，A结点的度为3；C结点的度为1；H结点的度为0； 4）树的度 树的度是指树中各个结点度的最大值。如图6.2中，由于A结点的度为3，其余结点的度都小于3，所以图6.2中树的度为3。 5）结点的层次 约定根结点的层次为1，其余结点的层次都是在其双亲结点层次上加1。如图6.2中，B结点的双亲结点为根结点A，根结点A的层次为1，所以B结点的层次为2；同理，E结点与F结点的层次是相同的，都为3。,一.树的定义和基本术语,2. 基本术语 6）树的高度 树的高度是指树中结点的最大层次数。如图6.2中，由于结点E、F、G、H、I的层次数都为3，其余结点的层次数都小于3，所以图6.2中树的高度为3。 7）森林 森林是m（m0）棵互不相交的树的集合。如图6.3即为一个森林。,一.树的定义和基本术语,1.定义 二叉树（binary tree）是n(n0)个结点组成的有限集合，并且每个结点最多有两棵子树。 当n=0时，二叉树被称为空二叉树 二叉树有以下五种基本形态： 空二叉树，如图6.4所示； 只有根结点的二叉树，如图6.5所示； 只有根结点和左子树的二叉树，如图6.6所示； 只有根结点和右子树的二叉树，如图6.7所示； 有根结点、左子树和右子树的二叉树，如图6.8所示；,二.二叉树,2.满二叉树 满二叉树是指除了叶子结点以外所有结点都存在左子树和右子树，并且所有叶子结点都在同一层上的二叉树。下图是一棵满二叉树。,二.二叉树,3.完全二叉树 完全二叉树是指叶子结点只出现在最下层和次下层，且最下层的叶子结点集中在树的左部的二叉树。下图是一棵完全二叉树。,二.二叉树,1.遍历二叉树 二叉树的遍历是指按照一定顺序，依次访问二叉树中所有结点，并且每个结点仅被访问一次。 二叉树的遍历一般可分为三种次序遍历，分别是先根遍历、中根遍历和后根遍历。 先根遍历：先访问根结点，再访问左子树，最后访问右子树。 中根遍历：先访问左子树，再访问根结点，最后访问右子树。 后根遍历：先访问左子树，再访问右子树，最后访问根结点。,三.遍历二叉树和线索二叉树,1.遍历二叉树 下图中，以A为根结点的二叉树先根遍历的结果为ABDECFGH,三.遍历二叉树和线索二叉树,1.遍历二叉树 二叉树先根遍历代码 public void preOrder(BinaryTreeNode r) if (r != null) System.out.print(r.getData() + ); preOrder(r.getLeft(); preOrder(r.getRight(); ,三.遍历二叉树和线索二叉树,2. 线索二叉树 线索二叉树的结点由5个部分组成：数据域、左对象域、右对象域、左标志域、右标志域。如图6.21为线索二叉树的结点。 （二叉树不变的，所以各个的标志不变） 当结点存在左子树时，左标志域为0，左对象域指向其左子树； 当结点不存在左子树时，左标志域为1，左对象域指向该结点的前驱结点；(指遍历的) 当结点存在右子树时，右标志域为0，右对象域指向其右孩子； 当结点不存在右子树时，右标志域为1，右对象域指向该结点的后继结点；(指遍历的),三.遍历二叉树和线索二叉树,2. 线索二叉树,三.遍历二叉树和线索二叉树,2. 线索二叉树,三.遍历二叉树和线索二叉树,1.树的存储结构 树的存储结构通常有顺序存储和链式存储，分别使用数组和链表来存储。,四.树和森林,1.树的存储结构,四.树和森林,1.树的存储结构 树的双亲表示法,四.树和森林,1.树的存储结构 树的孩子链表表示法,四.树和森林,2.树转换为二叉树 （1）加线,四.树和森林,2.树转换为二叉树 （2）抹线,四.树和森林,2.树转换为二叉树 （3）旋转,四.树和森林,2.森林转换为二叉树 森林,四.树和森林,2.森林转换为二叉树 （1）在森林最上层增加一个虚拟结点，并让该结点指向森林中每棵树的根结点,四.树和森林,2.森林转换为二叉树 （2）将树转换为二叉树,四.树和森林,2.森林转换为二叉树 （3）去掉根结点后，该二叉树即为森林转换成的二叉树,四.树和森林,3.二叉树转换为森林 二叉树,四.树和森林,3.二叉树转换为森林 （1）增加一个虚拟根结点，虚拟根结点指向二叉树的根结点,四.树和森林,3.二叉树转换为森林 （2）每个结点与其左孩子增加一条连线，结点与其左孩子的所有右孩子各增加一条连线,四.树和森林,3.二叉树转换为森林 （3）去掉每个结点之间原有连线。,四.树和森林,3.二叉树转换为森林 （4）去掉虚拟根结点,四.树和森林,3.二叉树转换为森林 （5）将连线逆时针旋转，整理成多棵树并列的森林,四.树和森林,4.树的遍历 树的遍历可以分为先根遍历和后根遍历。 树的先根遍历是首先访问树的根结点，然后从左至右逐一先序遍历根的每一棵子树。 树的后根遍历是首先从左至右逐一后根遍历树的每一棵子树，最后访问树的根结点。,四.树和森林,4.树的遍历 树的先根遍历结果为AQWPNSGCVF。 树的后根遍历结果为WPNQGCSFVA。,四.树和森林,5.森林的遍历 森林的遍历也分为先根遍历和后根遍历。 先根遍历是从左至右对森林中的每一棵树使用树的先根遍历方法逐一进行遍历。 后根遍历是从左至右对森林中的每一棵树使用树的后根遍历方法逐一进行遍历。,四.树和森林,5.森林的遍历 森林的先根遍历结果为：BDGEHCF。,四.树和森林,1.哈夫曼树 权值：赋予结点一个有意义的数字。 树的路径长度：从树的根结点到每个结点的路径长度之和。 结点的带权路径长度：结点到树根结点之间的路径长度与结点权值乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为WPL。,五.哈夫曼树及其应用,1.哈夫曼树 哈夫曼树就是由具有权值的叶子结点组成的带权路径长度（WPL）最小的二叉树。 哈夫曼算法的基本思想： 1）对于给定n个数据Ww1,w2,wn,将其分别放入n个结点内，并将这n个结点分别看作n棵二叉树，表示为T=T1,T2, ,Tn,。 2）从T中选取根结点权值最小的两棵二叉树组成一棵新的二叉树，并分别作为新二叉树的左右子树，新二叉树根结点的权值为左右子树根结点权值之和。 3）从T中删除第2步所使用的两棵二叉树，并将第2步所产生的二叉树加入到T中。 4）重复第2步与第3步，直到T中只有一棵二叉树为止，这棵二叉树就是数据W的哈夫曼树。,五.哈夫曼树及其应用,1.哈夫曼树,五.哈夫曼树及其应用,1.哈夫曼树 第1步，将数据W值放入结点内，并将其看作5棵二叉树T1,T2,T3,T4,T5。 T1 T2 T3 T4 T5,五.哈夫曼树及其应用,1.哈夫曼树 第2步，从T中选取权值最小的两棵二叉树，T5和T3组成一棵新的二叉树,五.哈夫曼树及其应用,1.哈夫曼树 第3步，从T中去掉T5和T3，并将第2步产生的二叉树放入集合T中,五.哈夫曼树及其应用,1.哈夫曼树 第4步，从新集合T中选出两个根结点最小的二叉树，组成新的二叉树,五.哈夫曼树及其应用,1.哈夫曼树 第5步，从T中去掉根结点权值为4和根结点权值为5的两棵二叉树，并将第4步产生的二叉树放入集合T中,五.哈夫曼树及其应用,1.哈夫曼树 第6步，从新集合T中选出两个根结点最小的二叉树，组成新的二叉树,五.哈夫曼树及其应用,1.哈夫曼树 第7步，从T中去掉根结点权值为7和根结点权值为9的两棵二叉树，并将第6步产生的二叉树放入集合T中,五.哈夫曼树及其应用,1.哈夫曼树 第8步，从新集合T中选出两个根结点最小的二叉树，即根结点权值为9和根结点权值为16的两棵二叉树，组成新的二叉树，并放入集合T中,五.哈夫曼树及其应用,2.哈夫曼编码 哈夫曼编码是一种变长的文本编码方案，它是依据文本中字符使用频率来进行编码。 在哈夫曼编码中，使用频率较高的字符其编码较短，使用频率较低的字符其编码较长，从而使所有字符的编码总长度为最短。,五.哈夫曼树及其应用,2.哈夫曼编码 哈夫曼编码步骤如下： 1)统计文本中字符出现频率，并按从高到低排列。 2)将两个最小的频率相加，并分别为两个频率标记为0或1。 3)将相加后的频率作为新的频率放入排列中。 4)重复第1步与第2步，直到排列中仅剩一个频率为止。 5)记录每个频率的标记路径，获得每个字符的哈夫曼编码。,五.哈夫曼树及其应用,2.哈夫曼编码 对文本“GGTSOTSGSG”文本进行哈夫曼编码。 首先，统计文本中字符的频率。G为0.4，T为0.2，S为0.3，O为0.1。 下面重复哈夫曼编码的第1步与第2步。,五.哈夫曼树及其应用,2.哈夫曼编码 原文本“GGTSOTSGSG”使用哈夫曼编码进行编码后的信息为“0011010111110100100”,五.哈夫曼树及其应用,