第06章树和二叉树.ppt
叶核亚,数据结构（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 树的表示目的：理解树结构。要求：掌握二叉树的表示和实现。重点：二叉树实现，哈夫曼树。难点：线索二叉树，哈夫曼树。,数据结构（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 树的表示法,图示法横向凹入表示法 ABEFCGDHIJ广义表表示 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 getNextSibling(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个结点的有限集合：空二叉树；由一个根结点、两棵互不相交的左子树和右子树组成。,数据结构（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无左孩子。若2i+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 inOrder();/中根次序遍历二叉树 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 二叉树的表示和实现,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;/数据元素 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版）,二叉树三种次序遍历的递归算法,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】输出二叉树中指定结点的所有祖先结点。,数据结构（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 中序线索二叉树,二叉树的中序线索化 中序线索二叉树类 中根次序遍历中序线索二叉树【例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，字符出现次数为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 树的遍历,树的先根遍历算法描述如下：访问根结点。按照从左到右的次序先根遍历根的每一棵子树。树的后根遍历算法描述如下：按照从左到右的次序后根遍历根的每一棵子树。访问根结点。,
