第06章节树与二叉树.pptVIP

叶核亚 数据结构（Java版）（第2版） 第0章 Java程序设计基础 第1章 绪论 第2章 线性表 第3章 栈与队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 排序 第10章 综合应用设计 第11章 Java开发运行环境 第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： 根（root）结点，它没有前驱结点。 其他结点分为m棵互不相交的子树。 6.1.2 树的术语 父母、孩子与兄弟结点 度 结点层次、树的高度 边、路径 无序树、有序树 森林 6.1.3 树的表示法 图示法 横向凹入表示法 A B E F C G D H I J 广义表表示 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.1 二叉树定义 二叉树（binary tree）是n个结点的有限集合： 空二叉树； 由一个根结点、两棵互不相交的左子树和右子树组成。 6.2.2 二叉树性质 性质1：若根结点的层次为1，则二叉树第i层最多有2i?1（i≥1）个结点。 性质2：在高度为k的二叉树中，最多有2k?1个结点（k≥0）。 性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。 性质4：一棵具有n个结点的完全二叉树，其高度 。 性质5：一棵具有n个结点的完全二叉树，对序号为i（0≤i＜n）的结点，有： 若i=0，则i为根结点，无父母结点；若i0，则i的父母结点序号为。 若2i+1＜n，则i的左孩子结点序号为2i+1；否则i无左孩子。 若2i+2＜n，则i的右孩子结点序号为2i+2；否则i无右孩子。 6.2.3 二叉树抽象数据类型 public interface BinaryTTreeE { //二叉树接口 boolean isEmpty(); //判断是否空二叉树 int count(); //返回二叉树的结点个数 int height();