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

《数据结构(java)-第6章树与二叉树-PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构(java)-第6章树与二叉树-PPT.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构(java)-第6 章树与二叉树1.树的定义树（tree）是由n(n0)个有限数据元素组成的数据集合，其中数据元素被称为结点。同时，树还必须满足以下两个条件：1.在树中有一个特殊的结点被称为根结点，它只有后继结点，没有前驱结点。2.除根结点以外，其余结点可以分为m（m0）个互不相交的集合T1，T2，Tm，其中每一个集合Ti（1im）本身又是一棵树。树T1，T2，Tm称为根结点的子树。一.树的定义和基本术语 1.树的定义一.树的定义和基本术语 AC D BF E I G H2.基本术语 1）双亲结点、子结点、兄弟结点 如图6.2 中，B 结点为E 结点的双亲结点；A 结点为D 结点的双亲

2、结点；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）结点的层次约定

3、根结点的层次为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 即为一个森林。一.树的定义和基本术语 C D BF E I G H1.定义 二叉树（binary tree）是n(n0)个结点组成的有限集合，

4、并且每个结点最多有两棵子树。当n=0 时，二叉树被称为空二叉树 二叉树有以下五种基本形态：空二叉树，如图6.4 所示；只有根结点的二叉树，如图6.5 所示；只有根结点和左子树的二叉树，如图6.6 所示；只有根结点和右子树的二叉树，如图6.7 所示；有根结点、左子树和右子树的二叉树，如图6.8 所示；二.二叉树大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流 大家有疑问的，可以询问和交流2.满二叉树 满二叉树是指除了叶子结点以外所有结点都存在左子树和右子树，并且所有叶子结点都在同一层上的二叉树。下图是一棵满二叉树。二.二叉树AC BE D G F3.完全二叉树 完全二叉树是指叶子结点只出

5、现在最下层和次下层，且最下层的叶子结点集中在树的左部的二叉树。下图是一棵完全二叉树。二.二叉树AC BE D1.遍历二叉树二叉树的遍历是指按照一定顺序，依次访问二叉树中所有结点，并且每个结点仅被访问一次。二叉树的遍历一般可分为三种次序遍历，分别是先根遍历、中根遍历和后根遍历。先根遍历：先访问根结点，再访问左子树，最后访问右子树。中根遍历：先访问左子树，再访问根结点，最后访问右子树。后根遍历：先访问左子树，再访问右子树，最后访问根结点。三.遍历二叉树和线索二叉树 1.遍历二叉树下图中，以A 为根结点的二叉树先根遍历的结果为ABDECFGH AC BD G FE H三.遍历二叉树和线索二叉树 1.

6、遍历二叉树二叉树先根遍历代码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，左对象域指向该结点的前驱结点；(指遍历

7、的)当结点存在右子树时，右标志域为0，右对象域指向其右孩子；当结点不存在右子树时，右标志域为1，右对象域指向该结点的后继结点；(指遍历的)三.遍历二叉树和线索二叉树 2.线索二叉树 AS GK U T三.遍历二叉树和线索二叉树 2.线索二叉树 0 A 0 0 G 0 0 S 1 1 U 1 1 T 1 1 K 1 null三.遍历二叉树和线索二叉树 1.树的存储结构 树的存储结构通常有顺序存储和链式存储，分别使用数组和链表来存储。四.树和森林 1.树的存储结构 四.树和森林 AC BD G F EH1.树的存储结构树的双亲表示法 四.树和森林 1.树的存储结构树的孩子链表表示法 四.树和森林

8、2.树转换为二叉树（1）加线四.树和森林 AC BD G F EH2.树转换为二叉树（2）抹线四.树和森林 AC BD G F EH2.树转换为二叉树（3）旋转四.树和森林 ACBDGF EH2.森林转换为二叉树 森林四.树和森林 C BD G F EH2.森林转换为二叉树（1）在森林最上层增加一个虚拟结点，并让该结点指向森林中每棵树的根结点 四.树和森林 C BD G F EHX2.森林转换为二叉树（2）将树转换为二叉树 四.树和森林 CBDGF EHX2.森林转换为二叉树（3）去掉根结点后，该二叉树即为森林转换成的二叉树 四.树和森林 CBDGF EH3.二叉树转换为森林 二叉树四.树和森

9、林 AC BE D3.二叉树转换为森林（1）增加一个虚拟根结点，虚拟根结点指向二叉树的根结点 四.树和森林 AC BE DX3.二叉树转换为森林（2）每个结点与其左孩子增加一条连线，结点与其左孩子的所有右孩子各增加一条连线 四.树和森林 AC BE DX3.二叉树转换为森林（3）去掉每个结点之间原有连线。四.树和森林 AC BE DX3.二叉树转换为森林（4）去掉虚拟根结点 四.树和森林 AC BE D3.二叉树转换为森林（5）将连线逆时针旋转，整理成多棵树并列的森林 四.树和森林 A CB ED4.树的遍历 树的遍历可以分为先根遍历和后根遍历。树的先根遍历是首先访问树的根结点，然后从左至右逐

10、一先序遍历根的每一棵子树。树的后根遍历是首先从左至右逐一后根遍历树的每一棵子树，最后访问树的根结点。四.树和森林 4.树的遍历 树的先根遍历结果为AQWPNSGCVF。树的后根遍历结果为WPNQGCSFVA。四.树和森林 AV QW P F NSC G5.森林的遍历 森林的遍历也分为先根遍历和后根遍历。先根遍历是从左至右对森林中的每一棵树使用树的先根遍历方法逐一进行遍历。后根遍历是从左至右对森林中的每一棵树使用树的后根遍历方法逐一进行遍历。四.树和森林 5.森林的遍历 森林的先根遍历结果为：BDGEHCF。四.树和森林 C BD G F EH1.哈夫曼树 权值：赋予结点一个有意义的数字。树的路

11、径长度：从树的根结点到每个结点的路径长度之和。结点的带权路径长度：结点到树根结点之间的路径长度与结点权值乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为WPL。五.哈夫曼树及其应用 1.哈夫曼树 哈夫曼树就是由具有权值的叶子结点组成的带权路径长度（WPL）最小的二叉树。哈夫曼算法的基本思想：1）对于给定n 个数据Ww1,w2,wn,将其分别放入n 个结点内，并将这n 个结点分别看作n 棵二叉树，表示为T=T1,T2,Tn,。2）从T 中选取根结点权值最小的两棵二叉树组成一棵新的二叉树，并分别作为新二叉树的左右子树，新二叉树根结点的权值为左右子树根结点权值之和。3）从T 中删

12、除第2 步所使用的两棵二叉树，并将第2 步所产生的二叉树加入到T 中。4）重复第2 步与第3 步，直到T 中只有一棵二叉树为止，这棵二叉树就是数据W 的哈夫曼树。五.哈夫曼树及其应用 1.哈夫曼树 五.哈夫曼树及其应用 3 5 971.哈夫曼树 第1 步，将数据W 值放入结点内，并将其看作5 棵二叉树T1,T2,T3,T4,T5。T1 T2 T3 T4 T5 五.哈夫曼树及其应用 9 3 7 5 11.哈夫曼树 第2 步，从T 中选取权值最小的两棵二叉树，T5 和T3 组成一棵新的二叉树 五.哈夫曼树及其应用 41 31.哈夫曼树 第3 步，从T 中去掉T5 和T3，并将第2 步产生的二叉树放

13、入集合T 中 五.哈夫曼树及其应用 9 4 7 53 11.哈夫曼树 第4 步，从新集合T 中选出两个根结点最小的二叉树，组成新的二叉树 五.哈夫曼树及其应用 4 53 191.哈夫曼树 第5 步，从T 中去掉根结点权值为4 和根结点权值为5 的两棵二叉树，并将第4 步产生的二叉树放入集合T 中 五.哈夫曼树及其应用 9 74 53 191.哈夫曼树 第6 步，从新集合T 中选出两个根结点最小的二叉树，组成新的二叉树 五.哈夫曼树及其应用 16971.哈夫曼树 第7 步，从T 中去掉根结点权值为7 和根结点权值为9 的两棵二叉树，并将第6 步产生的二叉树放入集合T 中 五.哈夫曼树及其应用 4

14、 53 19169 71.哈夫曼树 第8 步，从新集合T 中选出两个根结点最小的二叉树，即根结点权值为9 和根结点权值为16 的两棵二叉树，组成新的二叉树，并放入集合T 中 五.哈夫曼树及其应用 4 53 19169 7252.哈夫曼编码哈夫曼编码是一种变长的文本编码方案，它是依据文本中字符使用频率来进行编码。在哈夫曼编码中，使用频率较高的字符其编码较短，使用频率较低的字符其编码较长，从而使所有字符的编码总长度为最短。五.哈夫曼树及其应用 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 步。五.哈夫曼树及其应用