第06章+树和二叉树

《第06章+树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章树和二叉树6.1树及其抽象数据类型6.2二叉树及其抽象数据类型6.3二叉树的表示和实现6.4线索二叉树6.5哈夫曼编码与哈夫曼树6.6树的表示目的：理解树结构。要求：掌握二叉树的表示和实现。重点：二叉树实现，哈夫曼树。难点：线索二叉树，哈夫曼树。《数据结构（Java版）（第2版）》前面讨论的数据结构都属于线性结构，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述，而现实中的许多事物中的联系都是非线性的。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型就是其中十分重要的非线性结构，

2、可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如族谱、城市交通等。《数据结构（Java版）（第2版）》6.1树及其抽象数据类型6.1.1树定义6.1.2树的术语6.1.3树的表示法6.1.4树抽象数据类型《数据结构（Java版）（第2版）》6.1.1树定义树（tree）是由n（n≥0）个结点组成的有限集合。n=0的树称为空树；n＞0的树T：根（root）结点，它没有前驱结点。其他结点分为m棵互不相交的子树。《数据结构（Java版）（第2版）》3c3b11211133a2a1b1aa1a2c1例：家谱图《数据结构（Java版）（第2版）》树的逻辑意义

3、由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。ACGT2DHIT3JMBELKT1F《数据结构（Java版）（第2版）》从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一一条从根到该结点的路径；5）树是一种分枝结构（除根结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。JIACBDHGFEKLM《数据结构（Java版）（第2版）》6.1.2树的术语结点(node)：表示树中的元素，包括数据项及若干指向其子树的分

4、支。孩子(child)：结点子树的根称为该结点的孩子。父母，双亲(parents)：孩子结点的上层结点。兄弟(sibling)：同一双亲的孩子。《数据结构（Java版）（第2版）》6.1.2树的术语结点度(degree)：结点拥有的子树数叶结点：度为0的结点称为叶结点，或者称为终端结点分枝结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点树的度：一棵树中最大的结点度数结点的层(level)：从根结点算起，根为第一层，它的孩子为第二层……高度(depth)：树中结点的最大层次数《数据结构（Java版）（第2版）》6.

5、1.2树的术语路径、路径长度：如果一棵树的一串结点n0,n1,…,nk-1有如下关系：结点ni是ni+1的父结点（0≤i

6、的树的集合称为森林。任何一棵树，删去根结点就变成了森林。《数据结构（Java版）（第2版）》ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层：1结点M的层：4树的高（深）度：4结点F，G为堂兄弟结点A是结点F，G的祖先《数据结构（Java版）（第2版）》6.1.3树的表示法树型表示bacghdefij《数据结构（Java版）（第2版）》图形表示法：教师学生其他人员02级03级04

7、级05级……杭州电子科技大学计算机学院管理学院电子学院……叶子根子树《数据结构（Java版）（第2版）》凹入表表示abdeijfcghabcedghij《数据结构（Java版）（第2版）》abcedghij广义表（嵌套集合）表示ijdghabcea(b(d,e(i,j)),c(g,h))《数据结构（Java版）（第2版）》6.1.4树抽象数据类型publicinterfaceTTree{//树接口booleanisEmpty();//判断是否空树EgetRoot();//返回根结点元素EgetParent(Echild);//返回child的父母结点in

8、tgetChildCount(Epar