《数据结构》陈慧南_第05章树.ppt

数据结构 第5章 树 5.1?? 树的基本概念 5.2?? 二叉树 5.3?? 二叉树的遍历 5.5?? 树和森林 5.6?? 堆和优先权队列 5.7?? 哈夫曼树和哈夫曼编码 5.8?? 并查集和等价关系 5.1 树的基本概念 5.1.1 树的定义 定义5.1 树是包括n个结点的有限非空集合D，R是D中元素的序偶的集合，R满足以下特性： （1）有且仅有一个结点r?D，不存在任何结点v?D，v?r，使得v,r?R，称r为树的根 ； （2）除根r以外的所有结点u?D，都有且仅有一个结点v?D，v?u，使得v,u?R。 这样定义的树也称有根树，简称树。 5.1.2 基本术语 5.2 二叉树 5.2.1 二叉树的定义 5.2.2 二叉树的性质 5.2.3 二叉树ADT ADT BTree { 数据： 二叉树是结点的有限集合，它或者为空集合，或 者由一个根结点和两棵互不相交的左、右子二叉树组成。 运算： Create(); 构造一棵空二叉树。 Destroy()：撤消一棵二叉树。 IsEmpty():若二叉树为空，则返回true，否则返回false。 Clear():移去所有结点，成为空二叉树。 5.2.4 二叉树的存储表示 完全二叉树的顺序表示 5.2.5 二叉树类 程序5.1 二叉树结点类 templateclass T struct BTNode { BTNode(){ lChild=rChild=NULL;} BTNode(const T x) { element=x; lChild=rChild=NULL; } 5.2.6 实现二叉树基本运算 程序5.3 部分二叉树运算 template class T bool BinaryTreeT::Root(T x)const { if(root){ x=root-element; return true; } else return false; } 5.3 二叉树遍历 5.3.1 二叉树遍历算法 遍历一个有限的结点集合，意味着对该集合中的每个结点访问且仅访问一次。 先序遍历 template class T void BinaryTreeT::PreOrder( void (*Visit)(T x)) { PreOrder(Visit,root); } 5.3.3? 二叉树遍历的应用实例 求二叉树的结点数 template class T int BinaryTreeT::Size() { return Size(root); } 5.5 树和森林 5.5.1 森林与二叉树的转换 森林转换成二叉树：将森林中各树的根用线连起来，在树中，凡是兄弟用线连起来；去掉从双亲到除了第一个孩子以外的孩子的连线，只保留双亲到第一个孩子的连线；最后，使之稍微倾斜成习惯的二叉树形。其实，这里讨论的森林是指有序森林，也可将一般的森林视为有序森林来对待。 5.5.2 树和森林的存储表示 5.5.3 树和森林的遍历 按深度方向的遍历 由森林和二叉树的转换方法可知，森林中第一棵树的根即二叉树的根，第一棵树的子树组成的森林对应于二叉树的左子树，而除第一棵树外其余树组成的森林是二叉树的右子树，所以，对森林的先序遍历、中序遍历和后序遍历的结果应与对应二叉树的先序、中序和后序遍历的结果完全相同。 5.6 堆和优先权队列 5.6.1 堆 一个大小为n的堆是一棵包含n个结点的完全二叉树，该树中每个结点的关键字值大于等于其双亲结点的关键字值。完全二叉树的根称为堆顶，它的关键字值是整棵树上最小的。这样定义的堆称为最小堆 。还有最大堆 。 5.6.2 优先权队列ADT ADT PrioQueue{ 数据： n?0个元素的最小堆。 运算： Create()：建立一个空队列。 Destroy()：撤消一个队列。 IsEmpty()：若队列空，则返回true；否则返回false。 IsFull()：若队列满，则返回true；否则返回false。 5.6.3 优先权队列类 templateclass T class PrioQueue { public: PrioQueue(int mSize=20); ~PrioQueue(){delete[] q;}; b