《第06章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第06章树和二叉树.ppt（40页珍藏版）》请在三一文库上搜索。
1、叶核亚,数据结构（Java版） （第2版）,数据结构（Java版）（第2版）,第0章 Java程序设计基础 第1章 绪论 第2章 线性表 第3章 栈与队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 排序 第10章 综合应用设计 第11章 Java开发运行环境,数据结构（Java版）（第2版）,第6章 树和二叉树,6.1 树及其抽象数据类型 6.2 二叉树及其抽象数据类型 6.3 二叉树的表示和实现 6.4 线索二叉树 6.5 哈夫曼编码与哈夫曼树 6.6 树的表示 目的：理解树结构。 要求：掌握二叉树的表示和实现。 重点：二叉树实现，哈夫曼树。 难
2、点：线索二叉树，哈夫曼树。,数据结构（Java版）（第2版）,6.1 树及其抽象数据类型,6.1.1 树定义 6.1.2 树的术语 6.1.3 树的表示法 6.1.4 树抽象数据类型,数据结构（Java版）（第2版）,6.1.1 树定义,树（tree）是由n（n0）个结点组成的有限集合。n=0的树称为空树；n0的树T： 根（root）结点，它没有前驱结点。 其他结点分为m棵互不相交的子树。,数据结构（Java版）（第2版）,6.1.2 树的术语,父母、孩子与兄弟结点 度 结点层次、树的高度 边、路径 无序树、有序树 森林,数据结构（Java版）（第2版）,6.1.3 树的表示法,图示法 横向凹
3、入表示法 A B E F C G D H I J 广义表表示 A(B(E, F), C(G), D(H, I, J),数据结构（Java版）（第2版）,6.1.4 树抽象数据类型,public interface TTree /树接口 boolean isEmpty(); /判断是否空树 E getRoot(); /返回根结点元素 E getParent(E child); /返回child的父母结点 int getChildCount(E parent); /返回parent孩子结点数 E getFirstChild(E parent); /返回parent的孩子结点 E getNextSi
4、bling(E element); /返回下一个兄弟结点 void traverse(); /遍历树 void insert (E parent, E element); /插入作为parent的孩子 void remove(E parent); /删除以parent为根的子树 void clear(); /清空 ,数据结构（Java版）（第2版）,6.2 二叉树及其抽象数据类型,6.2.1 二叉树定义 6.2.2 二叉树性质 6.2.3 二叉树抽象数据类型,数据结构（Java版）（第2版）,6.2.1 二叉树定义,二叉树（binary tree）是n个结点的有限集合： 空二叉树； 由一个根结
5、点、两棵互不相交的左子树和右子树组成。,数据结构（Java版）（第2版）,6.2.2 二叉树性质,性质1：若根结点的层次为1，则二叉树第i层最多有2i1（i1）个结点。 性质2：在高度为k的二叉树中，最多有2k1个结点（k0）。 性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。,数据结构（Java版）（第2版）,性质4：一棵具有n个结点的完全二叉树，其高度 。 性质5：一棵具有n个结点的完全二叉树，对序号为i（0in）的结点，有： 若i=0，则i为根结点，无父母结点；若i0，则i的父母结点序号为。 若2i+1n，则i的左孩子结点序号为2i+1；否则i无左孩子。 若2
6、i+2n，则i的右孩子结点序号为2i+2；否则i无右孩子。,数据结构（Java版）（第2版）,6.2.3 二叉树抽象数据类型,public interface BinaryTTree /二叉树接口 boolean isEmpty(); /判断是否空二叉树 int count(); /返回二叉树的结点个数 int height(); /返回二叉树的高度 BinaryNode getRoot(); /返回二叉树的根结点 BinaryNode getParent(BinaryNode node); /返回node父母结点 void preOrder(); /先根次序遍历二叉树 void inOrde
7、r(); /中根次序遍历二叉树 void postOrder(); /后根次序遍历二叉树 void levelOrder(); /按层次遍历二叉树 BinaryNode search(E element); /查找并返回元素为element结点 void insert(BinaryNode p, E element, boolean leftChild); /插入element元素作为p结点的左/右孩子 void remove(BinaryNode p, boolean leftChild); /删除p的左/右子树 void clear(); /清空 ,数据结构（Java版）（第2版）,6.3
8、 二叉树的表示和实现,6.3.1 二叉树的存储结构 6.3.2 二叉树的二叉链表实现 6.3.3 二叉树的遍历 6.3.4 构造二叉树 6.3.5 二叉树的插入和删除操作 6.3.6 二叉树遍历的非递归算法 6.3.7 二叉树的层次遍历,数据结构（Java版）（第2版）,6.3.1 二叉树的存储结构,二叉树的顺序存储结构,数据结构（Java版）（第2版）,2.二叉树的链式存储结构,二叉链表 三叉链表,数据结构（Java版）（第2版）,6.3.2 二叉树的二叉链表实现,二叉链表结点类 public class BinaryNode /二叉树的二叉链表结点类 public E data; /数据元
9、素 public BinaryNode left, right; /分别指向左、右孩子 二叉树类 public class BinaryTree /二叉树类 protected BinaryNode root; /根结点 ,数据结构（Java版）（第2版）,6.3.3 二叉树的遍历,先根次序：访问根结点，遍历左子树，遍历右子树。 中根次序：遍历左子树，访问根结点，遍历右子树。 后根次序：遍历左子树，遍历右子树，访问根结点。 先根遍历序列：A B D G C E F H 中根遍历序列：D G B A E C H F 后根遍历序列：G D B E H F C A,数据结构（Java版）（第2版）,
10、二叉树三种次序遍历的递归算法,private void preOrder(BinaryNode p) /先根次序遍历以p结点为根的子树 if (p!=null) /若二叉树不空 System.out.print(p.data+“ “); /访问当前结点 preOrder(p.left); /按先根次序遍历当前结点的左子树 preOrder(p.right); /按先根次序遍历当前结点的右子树 【例6.1】 构造并遍历二叉树。 基于遍历的操作,数据结构（Java版）（第2版）,6.3.4 构造二叉树,先根和中根序列表示,数据结构（Java版）（第2版）,2.标明空子树的先根序列表示,【例6.2】
11、 输出二叉树中指定结点的所有祖先结点。,数据结构（Java版）（第2版）,3.广义表表示,数据结构（Java版）（第2版）,4.以完全二叉树的层次遍历序列构造链式存储结构的完全二叉树,【例6.3】 建立二叉链表表示的完全二叉树。,数据结构（Java版）（第2版）,6.3.5 二叉树的插入和删除操作,插入一个结点 删除一棵子树,数据结构（Java版）（第2版）,6.3.6 二叉树遍历的非递归算法,数据结构（Java版）（第2版）,6.3.7 二叉树的层次遍历,数据结构（Java版）（第2版）,6.4 线索二叉树,6.4.1 线索二叉树定义,数据结构（Java版）（第2版）,6.4.2 中序线索二
12、叉树,二叉树的中序线索化 中序线索二叉树类 中根次序遍历中序线索二叉树 【例6.4】 构造中序线索二叉树并进行中根次序遍历。 先根次序遍历中序线索二叉树 后根次序遍历中序线索二叉树,数据结构（Java版）（第2版）,1.二叉树的中序线索化,数据结构（Java版）（第2版）,4.先根次序遍历中序线索二叉树,数据结构（Java版）（第2版）,5.后根次序遍历中序线索二叉树,数据结构（Java版）（第2版）,6.5 哈夫曼编码与哈夫曼树,6.5.1 哈夫曼编码 6.5.2 哈夫曼树,数据结构（Java版）（第2版）,6.5.1 哈夫曼编码,存储“AAAABBBCDDBBAAA”，字符集A、B、D、C
13、，字符出现次数为7、5、2、1，频率为0.47、0.33、0.13、0.07，哈夫曼编码过程为：,数据结构（Java版）（第2版）,6.5.2 哈夫曼树,二叉树的带权外路径长度,数据结构（Java版）（第2版）,4.构造哈夫曼树并获得哈夫曼编码,哈夫曼树定义为带权外路径长度最短的二叉树。 哈夫曼树不唯一,数据结构（Java版）（第2版）,构造哈夫曼树,数据结构（Java版）（第2版）,例6.5 构造哈夫曼树并获得哈夫曼编码。,数据结构（Java版）（第2版）,图6.35 哈夫曼树和哈夫曼编码,若权值集合5,29,7,8,14,23,3,11对应字符AH,数据结构（Java版）（第2版）,6.6 树的表示 6.6.1 树的存储结构,孩子链表 孩子兄弟链表,数据结构（Java版）（第2版）,6.6.2 树的遍历,树的先根遍历算法描述如下： 访问根结点。 按照从左到右的次序先根遍历根的每一棵子树。 树的后根遍历算法描述如下： 按照从左到右的次序后根遍历根的每一棵子树。 访问根结点。,