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

《数据结构(java)-第6章树与二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基本内容1.树的定义和基本术语第6章树与二叉树2.二叉树3.遍历二叉树和线索二叉树4.树和森林5.哈夫曼树及其应用1.树的定义树（tree）是由n(n≥0)个有限数据元素组成的数据集合，其中数据元素被称为结点。同时，树还必须满足以下两个条件：在树中有一个特殊的结点被称为根结点，它只有后继结点，没有前驱结点。除根结点以外，其余结点可以分为m（m≥0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为根结点的子树。一.树的定义和基本术语1.树的定义一.树的定义和基本术语ACDBFEIGH

2、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）树的度树的度是指树中各个结点度的最大值。

3、如图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（m≥0）棵互不相交的树的集合。如图6.3即为一个森林。

4、一.树的定义和基本术语CDBFEIGH1.定义二叉树（binarytree）是n(n≥0)个结点组成的有限集合，并且每个结点最多有两棵子树。当n=0时，二叉树被称为空二叉树二叉树有以下五种基本形态：空二叉树，如图6.4所示；只有根结点的二叉树，如图6.5所示；只有根结点和左子树的二叉树，如图6.6所示；只有根结点和右子树的二叉树，如图6.7所示；有根结点、左子树和右子树的二叉树，如图6.8所示；二.二叉树2.满二叉树满二叉树是指除了叶子结点以外所有结点都存在左子树和右子树，并且所有叶子结点都在同一层上的二叉树。下图是一棵满二叉树。二.二叉树AC

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

6、树先根遍历的结果为ABDECFGHACBDGFEH三.遍历二叉树和线索二叉树1.遍历二叉树二叉树先根遍历代码publicvoidpreOrder(BinaryTreeNoder){if(r!=null){System.out.print(r.getData()+"");preOrder(r.getLeft());preOrder(r.getRight());}}三.遍历二叉树和线索二叉树2.线索二叉树线索二叉树的结点由5个部分组成：数据域、左对象域、右对象域、左标志域、右标志域。如图6.21为线索二叉树的结点。（二叉树不变的，所以各个的标志不变

7、）当结点存在左子树时，左标志域为0，左对象域指向其左子树；当结点不存在左子树时，左标志域为1，左对象域指向该结点的前驱结点；(指遍历的)当结点存在右子树时，右标志域为0，右对象域指向其右孩子；当结点不存在右子树时，右标志域为1，右对象域指向该结点的后继结点；(指遍历的)三.遍历二叉树和线索二叉树2.线索二叉树ASGKUT三.遍历二叉树和线索二叉树2.线索二叉树0A00G00S11U11T11K1null三.遍历二叉树和线索二叉树1.树的存储结构树的存储结构通常有顺序存储和链式存储，分别使用数组和链表来存储。四.树和森林1.树的存储结构四.树和森

8、林ACBDGFEH1.树的存储结构树的双亲表示法四.树和森林1.树的存储结构树的孩子链表表示法四.树和森林2.树转换为二叉树（1）加线四.树和森林AC