蔡明志数据结构java版第6章.ppt

第6章 树结构 6.1 树的一些专有名词 6.2 二叉树 6.3 二叉树的表示方法 6.4 二叉树遍历 6.5 二叉查找树 6.6 其他论题 6.7 程序集锦 6.8 思考题 第6章 树结构 树结构是指各项数据可通过边（edge）连接起来的组织方法。 树的定义如下：树是由结点（node）和边（edge）所组成的集合。 它包括 ①有一特殊的结点，称为根（root）； ②其余的结点分成n个（n ≥ 0）互斥的集合T1，T2，…，Tn，每一个集合都是一棵树。T1，T2，…，Tn是根的子树（subtree）。 6.1 树的一些专有名词 通过下面树的表示法介绍树的一些专有名词： 1. 结点与边：结点代表某项数据，而边是指由一结点到另一结点的分支。图中有14个结点，其结点的数据是英文字母。 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的子结点。 6.1 树的一些专有名词 4. 兄弟结点：相同父结点的子结点。如图所示，B、C、D为兄弟结点。 5. 非终端结点：有子结点的结点。如图所示，除了J、K、L、G、M、N、I外，其余的结点皆为非终端结点。 6. 终端结点或叶子结点：没有子结点的结点称为终端结点，如图所示，J、K、L、G、M、N、I皆为叶子结点。 6.1 树的一些专有名词 7. 结点的度：一个结点的度是它拥有的子结点数。如图所示A的度为3，而B的度为2。而一棵树的度是指树内各结点所拥有的度的最大值，如图所示，这棵树的度为3。 8. 层次：树中结点世代的关系，一代为一个层次，根的层为1，如图所示，此树层次为4。 9. 高度：树中某结点的高度表示此结点到叶子结点的最长路径（path）长度，如图所示的A结点高度为3，C结点的高度为1，而树的高度为树中最大高度。如图所示，此棵树的高度为3。 6.1 树的一些专有名词 10. 深度：某个结点的深度为根至此结点的路径长度，如图所示的C结点其深度为1，而M、N结点的深度为3，同理，E结点的深度为2。 6.2 二叉树 二叉树是由结点所组成的有限集合，这个集合不是空集合就是由左子树（left subtree）和右子树（right subtree）所组成的。 二叉树与一般树不同的地方是： 1. 二叉树的结点个数可以是零，而一般树至少由一个结点所组成。 2. 二叉树有排列顺序的关系，而一般树则没有。 3. 二叉树中每一结点的度至多为2，而一般树无此限制。 练习题 有一棵树如图所示。 试回答下列问题： （1）它是否是一棵二叉树？ （2）它是否是一棵满二叉树？ （3）它是否是一棵完全二叉树？ 6.3 二叉树的表示方法 如何将二叉树的结点存储在一维数组中呢？ 可以想像此二叉树为满二叉树，第I层具有2i-1个结点，依此类推。假若是三叉树，第I层则有3i-1个结点。也可以利用链表的方式来解决这些问题，将每一结点划分3个字段，左指针（Left Link）以LLINK表示，数据（data）以DATA表示，右指针（Right Link）以RLINK表示，如下图所示。 6.4 二叉树遍历 二叉树的遍历（traversal）可分成3种： 1． 中序遍历（inorder）：先遍历左子树，然后遍历树根，再遍历右子树。 2． 先序遍历（preorder）：先遍历树根，然后遍历左子树，再遍历右子树。 3． 后序遍历（postorder）：先遍历左子树，然后遍历右子树，再遍历树根。 （举例p125） 6.5 二叉查找树 二叉查找树（Binary Search Tree）的定义为二叉查找树可以是空集点，假设不是空集合，则树中的每一结点（node）均含有一关键字（key value），而且具有下列特性： 1． 在左子树的所有关键字均小于根的关键字。 2． 在右子树的所有关键字均大于根的关键字。 3． 左子树和右子树是二叉查找树。 6.5 二叉查找树 6.5.1 二叉查找树的插入与删除 6.5.2 二叉查找树的查询 6.5.1 二叉查找树的插入与删除 由于二叉查找树的特性是左子树关键字均小于根的关键字，而右子树的关键字均大于根的关键字。因此加入某一关键字只要逐一比较，依据关键字的大小往右或往左，便可找到此关键字插入的位置。 删除某一结点时，若删除的是叶结点，则直接删除，假若删除的不是叶结点，则在左子树找到最大的结点或在右子树找到最小的结点，取代将被删除的结点。 6.5.2