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

《蔡明志数据结构java版第6章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树结构6.1树的一些专有名词6.2二叉树6.3二叉树的表示方法6.4二叉树遍历6.5二叉查找树6.6其他论题6.7程序集锦6.8思考题1第6章树结构树结构是指各项数据可通过边（edge）连接起来的组织方法。树的定义如下：树是由结点（node）和边（edge）所组成的集合。它包括①有一特殊的结点，称为根（root）；②其余的结点分成n个（n≥0）互斥的集合T1，T2，…，Tn，每一个集合都是一棵树。T1，T2，…，Tn是根的子树（subtree）。26.1树的一些专有名词通过下面树的表示法介绍树的一些专有名词：1.结点与边：结点代表某

2、项数据，而边是指由一结点到另一结点的分支。图中有14个结点，其结点的数据是英文字母。36.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树的一些专有名词4.兄弟结点：相同父结点的子结点。如图所示，B、C、D为兄弟结点。5.非终端结点：有子结点的结点。如图所示，除了J、K、L、G

3、、M、N、I外，其余的结点皆为非终端结点。6.终端结点或叶子结点：没有子结点的结点称为终端结点，如图所示，J、K、L、G、M、N、I皆为叶子结点。56.1树的一些专有名词7.结点的度：一个结点的度是它拥有的子结点数。如图所示A的度为3，而B的度为2。而一棵树的度是指树内各结点所拥有的度的最大值，如图所示，这棵树的度为3。8.层次：树中结点世代的关系，一代为一个层次，根的层为1，如图所示，此树层次为4。9.高度：树中某结点的高度表示此结点到叶子结点的最长路径（path）长度，如图所示的A结点高度为3，C结点的高度为1，而树的高度为树中最大高

4、度。如图所示，此棵树的高度为3。66.1树的一些专有名词10.深度：某个结点的深度为根至此结点的路径长度，如图所示的C结点其深度为1，而M、N结点的深度为3，同理，E结点的深度为2。76.2二叉树二叉树是由结点所组成的有限集合，这个集合不是空集合就是由左子树（leftsubtree）和右子树（rightsubtree）所组成的。二叉树与一般树不同的地方是：1.二叉树的结点个数可以是零，而一般树至少由一个结点所组成。2.二叉树有排列顺序的关系，而一般树则没有。3.二叉树中每一结点的度至多为2，而一般树无此限制。8练习题有一棵树如图所示。试回

5、答下列问题：（1）它是否是一棵二叉树？（2）它是否是一棵满二叉树？（3）它是否是一棵完全二叉树？96.3二叉树的表示方法如何将二叉树的结点存储在一维数组中呢？可以想像此二叉树为满二叉树，第I层具有2i-1个结点，依此类推。假若是三叉树，第I层则有3i-1个结点。也可以利用链表的方式来解决这些问题，将每一结点划分3个字段，左指针（LeftLink）以LLINK表示，数据（data）以DATA表示，右指针（RightLink）以RLINK表示，如下图所示。106.4二叉树遍历二叉树的遍历（traversal）可分成3种：1．中序遍历（inor

6、der）：先遍历左子树，然后遍历树根，再遍历右子树。2．先序遍历（preorder）：先遍历树根，然后遍历左子树，再遍历右子树。3．后序遍历（postorder）：先遍历左子树，然后遍历右子树，再遍历树根。（举例p125）116.5二叉查找树二叉查找树（BinarySearchTree）的定义为二叉查找树可以是空集点，假设不是空集合，则树中的每一结点（node）均含有一关键字（keyvalue），而且具有下列特性：1．在左子树的所有关键字均小于根的关键字。2．在右子树的所有关键字均大于根的关键字。3．左子树和右子树是二叉查找树。126.5

7、二叉查找树6.5.1二叉查找树的插入与删除6.5.2二叉查找树的查询136.5.1二叉查找树的插入与删除由于二叉查找树的特性是左子树关键字均小于根的关键字，而右子树的关键字均大于根的关键字。因此加入某一关键字只要逐一比较，依据关键字的大小往右或往左，便可找到此关键字插入的位置。删除某一结点时，若删除的是叶结点，则直接删除，假若删除的不是叶结点，则在左子树找到最大的结点或在右子树找到最小的结点，取代将被删除的结点。146.5.2二叉查找树的查询如何决定关键字X是否在二叉查找树中，首先X先与根比较，若X等于根表示找到，如果X大于树根，则往右子

8、树去查找；否则，到左子树去查找。二叉查找树的查询程序如下：//查询二叉查找树tree中的data值，tree中的每个结点都有3个字段//llink、key、rlink，当data不在tree中