数据结构(java)-第6章树与二叉树

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