第六章树和二叉树-1.ppt

第六章 树和二叉树 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： 有且仅有一个特定的称为根（Root）的结点。它没有前驱结点。 其余的结点可分为m(m≥0)个互不相交的子集T0,T1,…，Tm-1，其中每个子集本身又是一棵树，并称其为根的子树。 特点： 只包含一个结点的树必然仅由根结点构成 树中各子树是互不相交的集合 当n1时，n个结点的树借助于少于n个结点的树来定义。递归定义 6.1.2 树的术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m?0)棵互不相交的树的集合 6.1.2 树的术语 设树中X结点是Y结点的父母结点，有序对(X,Y)称为连接这两个结点的分支，也称为边（edge） 。 设(X0,X1,…,Xk-1)是由树中结点组成的一个序列，且( Xi-1， Xi)(0≤ik-1)都是树中的边，则该序列称为从X0到Xk-1的一条路径（path）。 路径长度（path length）为路径上的边数。 6.1.2 树的术语 无序树与：在树的定义中，结点的子树T0,T1,…，Tm-1之间没有次序，可以交换位置。 有序树（ordered tree）：结点的子树T0,T1,…，Tm-1之间有次序，不能交换位置。 和线性结构的比较 6.1.3 树的表示法 图示法 横向凹入表示法 A B E F C G D H I J 6.1.4 树抽象数据类型 public interface TTreeE { //树接口 boolean isEmpty(); //判断是否空树 E getRoot(); //返回根结点元素 E getParent(E child); //返回child的父母结点 int getChildCount(E parent); //返回parent孩子结点数 E getFirstChild(E parent); //返回parent的孩子结点 E getNextSibling(E element); //返回下一个兄弟结点 void traverse(); //遍历树 void insert (E parent, E element); //插入作为parent的孩子 void remove(E parent); //删除以parent为根的子树 void clear(); //清空 } 6.2 二叉树及其抽象数据类型 6.2.1 二叉树定义 6.2.2 二叉树性质 6.2.3 二叉树抽象数据类型 6.2 二叉树 定义 定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态 二叉树性质 性质1： 几种特殊形式的二叉树 满二叉树 定义： 性质5：一棵具有n个结点的完全二叉树，对序号为i（0