《蔡明志数据结构java版第6章.ppt》由会员分享，可在线阅读，更多相关《蔡明志数据结构java版第6章.ppt（23页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 树结构树结构 6.1 树的一些专有名词6.2 二叉树6.3 二叉树的表示方法 6.4 二叉树遍历6.5 二叉查找树 6.6 其他论题6.7 程序集锦6.8 思考题1第第6 6章章 树结构树结构树结构是指各项数据可通过边（edge）连接起来的组织方法。 树的定义如下：树是由结点（node）和边（edge）所组成的集合。它包括有一特殊的结点，称为根（root）；其余的结点分成n个（n 0）互斥的集合T1，T2，Tn，每一个集合都是一棵树。T1，T2，Tn是根的子树（subtree）。 26.1 6.1 树的一些专有名词树的一些专有名词 通过下面树的表示法介绍树的一些专有名词：1.
2、结点与边：结点代表某项数据，而边是指由一结点到另一结点的分支。图中有14个结点，其结点的数据是英文字母。 36.1 6.1 树的一些专有名词树的一些专有名词2. 祖先结点与子孙结点：若从结点X有一条路径通往结点Y，则X是Y的祖先，Y是X的子孙。如上图所示，结点A可通往K，故称A是K的祖先，而K是A的子孙。3. 父结点与子结点：若结点X直接到结点Y，则称X为Y的父结点，Y为X的子结点。如上图所示，A为B、C、D的父结点，B、C、D为A的子结点。 46.1 6.1 树的一些专有名词树的一些专有名词4. 兄弟结点：相同父结点的子结点。如图所示，B、C、D为兄弟结点。5. 非终端结点：有子结点的结点。
3、如图所示，除了J、K、L、G、M、N、I外，其余的结点皆为非终端结点。 6. 终端结点或叶子结点：没有子结点的结点称为终端结点，如图所示，J、K、L、G、M、N、I皆为叶子结点。 56.1 6.1 树的一些专有名词树的一些专有名词7. 结点的度：一个结点的度是它拥有的子结点数。如图所示A的度为3，而B的度为2。而一棵树的度是指树内各结点所拥有的度的最大值，如图所示，这棵树的度为3。8. 层次：树中结点世代的关系，一代为一个层次，根的层为1，如图所示，此树层次为4。9. 高度：树中某结点的高度表示此结点到叶子结点的最长路径（path）长度，如图所示的A结点高度为3，C结点的高度为1，而树的高度为
4、树中最大高度。如图所示，此棵树的高度为3。66.1 6.1 树的一些专有名词树的一些专有名词10. 深度：某个结点的深度为根至此结点的路径长度，如图所示的C结点其深度为1，而M、N结点的深度为3，同理，E结点的深度为2。76.2 6.2 二叉树二叉树 二叉树是由结点所组成的有限集合，这个集合不是空集合就是由左子树（left subtree）和右子树（right subtree）所组成的。二叉树与一般树不同的地方是： 1.二叉树的结点个数可以是零，而一般树至少由一个结点所组成。2.二叉树有排列顺序的关系，而一般树则没有。3.二叉树中每一结点的度至多为2，而一般树无此限制。 8练习题练习题 有一棵
5、树如图所示。试回答下列问题：（1）它是否是一棵二叉树？（2）它是否是一棵满二叉树？（3）它是否是一棵完全二叉树？ 96.3 6.3 二叉树的表示方法二叉树的表示方法 如何将二叉树的结点存储在一维数组中呢？可以想像此二叉树为满二叉树，第I层具有2i-1个结点，依此类推。假若是三叉树，第I层则有3i-1个结点。也可以利用链表的方式来解决这些问题，将每一结点划分3个字段，左指针（Left Link）以LLINK表示，数据（data）以DATA表示，右指针（Right Link）以RLINK表示，如下图所示。 106.4 6.4 二叉树遍历二叉树遍历 二叉树的遍历（traversal）可分成3种：1
6、中序遍历（inorder）：先遍历左子树，然后遍历树根，再遍历右子树。2 先序遍历（preorder）：先遍历树根，然后遍历左子树，再遍历右子树。3 后序遍历（postorder）：先遍历左子树，然后遍历右子树，再遍历树根。（举例p125） 116.5 6.5 二叉查找树二叉查找树 二叉查找树（Binary Search Tree）的定义为二叉查找树可以是空集点，假设不是空集合，则树中的每一结点（node）均含有一关键字（key value），而且具有下列特性：1在左子树的所有关键字均小于根的关键字。2在右子树的所有关键字均大于根的关键字。3左子树和右子树是二叉查找树。 126.5 6.5 二
7、叉查找树二叉查找树 6.5.1 二叉查找树的插入与删除6.5.2 二叉查找树的查询 136.5.1 6.5.1 二叉查找树的插入与删除二叉查找树的插入与删除由于二叉查找树的特性是左子树关键字均小于根的关键字，而右子树的关键字均大于根的关键字。因此加入某一关键字只要逐一比较，依据关键字的大小往右或往左，便可找到此关键字插入的位置。 删除某一结点时，若删除的是叶结点，则直接删除，假若删除的不是叶结点，则在左子树找到最大的结点或在右子树找到最小的结点，取代将被删除的结点。146.5.2 6.5.2 二叉查找树的查询二叉查找树的查询 如何决定关键字X是否在二叉查找树中，首先X先与根比较，若X等于根表示
8、找到，如果X大于树根，则往右子树去查找；否则，到左子树去查找。二叉查找树的查询程序如下：/ 查询二叉查找树tree中的data值，tree中的每个结点都有3个字段/ llink、key、rlink，当data不在tree中时，返回node的值为null/ llink(空的二叉树)=rlink=null156.5.2 6.5.2 二叉查找树的查询二叉查找树的查询public Node_type search(Node_type tree, int data, Node_type node) node=tree; while(node!=null) if(datanode.key) node=no
9、de.rlink;else return node; 166.6 6.6 其他论题其他论题 1 将树和森林转换为二叉树 一般树转换为二叉树，步骤如下：（1）将结点的所有兄弟（sibling）连接在一起。（2）把所有不是连到最左子结点的子结点链接删除。（3）顺时针旋转45。176.6 6.6 其他论题其他论题森林转换为二叉树，步骤如下：（1）先将森林中的每棵树转换为二叉树（不旋转45）。（2）把所有二叉树利用根结点全部链接在一起 。（3）旋转45。186.6 6.6 其他论题其他论题2 决定唯一的二叉树 每一棵二叉树都有唯一的一对中序与先序序列，也有唯一的中序与后序序列。如给予中序序列是FDHG
10、IBEAC，而先序序列是ABDFGHIEC。由先序系列知，A是根，且由中序序列可知C是A的右子结点。由先序序列知B是FDHGIE的父结点，并从中序序列知E是B的右子结点。196.6 6.6 其他论题其他论题再由先序序列知D是FHGI的父结点，由中序知F是D的左子结点，HGI是D的右子结点。最后由先序序列可知G是HI的父结点，并从中序序列可知H是G的左子结点，I是G的右子结点。20练习题练习题 1将如图所示的一般树转换为二叉树。2已知有一棵二叉树，中序序列为ECBDA，先序序列为ABCED，试画出此棵二叉树。3已知有一棵二叉树，中序序列为DFBAEGC，后序序列为FDBGECA，试画出其所对应的二叉树。216.7 6.7 程序集锦程序集锦 二叉查找树结点的增加与删除 226.8 6.8 思考题思考题 1. 试说明一般树与二叉树有何不同?并解释为何要将一般树转换为二叉树。2. 有一棵二叉树如图所示。请列出所有的叶结点、非叶结点及每一结点的层（level）。3. 将思考题2的二叉树以下列几种形式表示出来：（1）array（2）link（3）thread link 23
