第6章 树和二叉树-课件.pptVIP

第6章 树和二叉树 树型结构是一类非常重要的非线性结构，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象。 因此在计算机领域里有着广泛应用。如： 操作系统中的文件管理 编译程序中的语法结构 数据库系统信息组织形式 主要内容 6.1 树及其抽象数据类型 6.2 二叉树及其抽象数据类型 6.3 二叉树的表示和实现 6.4 线索二叉树 6.5 哈夫曼编码与哈夫曼树 6.6 树的表示 目的：理解树结构。 要求：掌握二叉树的表示和实现。 重点：二叉树实现，哈夫曼树。 难点：哈夫曼树。 6.1 树及其抽象数据类型 6.1.1 树定义 6.1.2 树的术语 6.1.3 树的表示法 6.1.4 树抽象数据类型 6.1.1 树定义 树（tree）是由n（n≥0）个结点组成的有 限集合。n=0的树称为空树；n＞0的树T： 有且仅有一个结点n0，它没有前驱结点， 只有后继结点。n0称作树的根（root）结点。 除结点外n0 ， 其余的每一个结点都有且 仅有一个直接前驱结点；有零个或多个直 接后继结点。 一颗大树分成几个大的分枝，每个大分枝再分成几个小分枝，小分枝再分成更小的分枝，… ，每个分枝也都是一颗树，由此我们可以给出树的递归定义。 树（tree）是由n（n≥0）个结点组成的有 限集合。n=0的树称为空树；n＞0的树T： 有且仅有一个结点n0，它没有前驱结点，只有后继结点。n0称作树的根（root）结点。 除根结点之外的其他结点分为m（m≥0）个互不相交的集合T0，T1，…，Tm-1，其中每个集合Ti（0≤i＜m）本身又是一棵树，称为根的子树（subtree）。 举例 6.1.2 树的术语 父母、孩子与兄弟结点 度 结点层次、树的高度 边、路径 无序树、有序树 森林 1.父母、孩子与兄弟结点 结点的直接前驱结点称为父母（parents）结点。 结点的直接后继结点称为孩子（child）结点。 拥有同一个父母结点的多个结点之间称为兄弟（sibling）结点。 结点的祖先（ancestor）是指从根结点到其父母结点所经过的所有结点。 结点的后代（descendant）是指该结点的所有孩子结点，以及孩子的孩子等。 祖先与后代的关系则是对父子关系的延伸，其定义了树中结点的纵向次序 。 2.度 结点的度（degree）是指结点所拥有子树的棵数。 度为零的结点称为叶子（leaf）或者终端结点 度不为零的结点称为分支结点或者非终端结点、非叶结点。 树的度是指树中各结点度的最大值。 3.结点层次、树的高度 结点的层次（level）属性反映结点处于树中的层次位置。 约定根结点的层次为1，其余结点的层次是其父母结点的层次加1. 树的高度（height）或深度（depth）是树中结点的最大层次数。 4.边、路径 设树中X结点是Y结点的父母结点，有序对（X，Y）称为连接这两个结点的分支，也称为边（edge）。 设（X0，X1，…，Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（0≤i＜k-1）都是树中的边，则该序列称为X0到Xk-1的一条路径（path）。 路径长度（path length）为路径上的边数。 5.无序树、有序树 若把树中每个结点的各子树看成从左到右有次序的（即不能互换），则称该树为有序树（Ordered Tree）；否则称为无序树（Unordered Tree） 如果规定k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，则定义了树中结点的横向次序 6.森林 森林（Forest）是m（m≥0）棵互不相交树的集合。 给森林加上一个根结点就变成一棵树。 将树的根结点删除就变成森林。 6.1.3 树的表示法 1、用二元组描述 2、用树型图表示 3、用文氏图表示 4、用凹入图表示 5、用广义表表示 1、树的逻辑结构可以用二元组描述为： Group=（D，R） D={A,B,C,D,E,F,G,H,I,J} R={A,B,A,C,A,D,B,E,B,F,D,G,D,H,F,I,F,J} 2、用树型图表示3、用文氏图表示 4、用凹入图表示5、用广义表图表示 6.1.4 树抽象数据类型(TTree.java) public interface TTreeE { //树接口 boolean isEmpty(); //判断是否空树 E getRoot(); //返回根结点元素 E getParent(E child);