《数据结构——使用C++语言描述 第2版 普通高等教育“十一五”国家级规划教材 江苏省高等学校精品教材 教学课件 ppt 作者 陈慧南 《数据结构A》第05章》由会员分享，可在线阅读，更多相关《数据结构——使用C++语言描述 第2版 普通高等教育“十一五”国家级规划教材 江苏省高等学校精品教材 教学课件 ppt 作者 陈慧南 《数据结构A》第05章（119页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学计算机学院 陈慧南 2006年9月,数据结构,Data Structures in C+,南京邮电大学计算机学院 陈慧南 2006年9月,第5章 树,南京邮电大学计算机学院 陈慧南 2006年9月,5.1 树的基本概念 5.2 二叉树 5.3 二叉树的遍历 5.5 树和森林 5.6 堆和优先权队列 5.7 哈夫曼树和哈夫曼编码 5.8 并查集和等价关系,南京邮电大学计算机学院 陈慧南 2006年9月,5.1 树的基本概念,南京邮电大学计算机学院 陈慧南 2006年9月,树形结构是元素之间有着分层关系的结构，它类似于自然界中的树。这是一类很重要的非线性数据结构。 一方面，计算机应用中
2、，常常出现嵌套的数据，树结构提供了对该类数据的自然表示。另一方面利用树结构，我们可以有效地解决一些算法问题。,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,5.1.1 树的定义,定义5.1 树是包括n个结点的有限非空集合D，R是D中元素的序偶的集合，R满足以下特性： （1）有且仅有一个结点rD，不存在任何结点vD，vr，使得R，称r为树的根 ； （2）除根r以外的所有结点uD，都有且仅有一个结点vD，vu，使得R。 这样定义的树也称有根树，简称树。,南京邮电大学计算机学院 陈慧南 2006年9月,定义5.2 树是包括n个结点的有限非空集合T，其
3、中，一个特定的结点r称为根，其余结点 T-r划分成m（m0）个互不相交的子集T1,T2,Tm，其中，每个子集都是树，被称为树根r的子树。,南京邮电大学计算机学院 陈慧南 2006年9月,5.1.2 基本术语,树中元素常称为结点 。根和它的子树根（如果存在）之间形成一条边 。如果从某个结点沿着树中的边可到达另一个结点，则称这两个结点间存在一条路径 。,南京邮电大学计算机学院 陈慧南 2006年9月,若一个结点有子树，那么该结点称为子树根的双亲，子树的根是该结点的孩子。有相同双亲的结点互为兄弟。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点路径上的所有结点都是该结点的祖先 。,
4、南京邮电大学计算机学院 陈慧南 2006年9月,一个结点拥有的子树数称为该结点的度。度为零的结点称为叶子，其余结点称为分支结点。树中结点的最大的度称为树的度。 树是层次结构的，规定根结点的层次为1，其结点的层次等于其双亲结点的层次加1。树中结点的最大层次称为该树的高度。,南京邮电大学计算机学院 陈慧南 2006年9月,如果树中结点的各子树之间的次序是不重要的，可以交换位置，这样的树称为无序树。也就是我们通常所说的树。如果将树中结点的各棵子树看成是从左到右有次序的，则称该树为有序树。从左到右，可分别称这些子树为第一子树，第二子树等等。 森林是树的集合。果园或称有序森林是有序树的有序集合。,南京邮
5、电大学计算机学院 陈慧南 2006年9月,5.2 二叉树,南京邮电大学计算机学院 陈慧南 2006年9月,5.2.1 二叉树的定义,定义5.3 二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两棵互不相交的，称为该根的左子树和右子树的二叉树组成。,南京邮电大学计算机学院 陈慧南 2006年9月,二叉树的五种基本形态,二叉树与树的区别,二叉树可以为空二叉树 二叉树结点的子树分为左、右子树,南京邮电大学计算机学院 陈慧南 2006年9月,5.2.2 二叉树的性质,性质5.1 二叉树的第i(i1)层上至多有2i-1 个结点。,证明：当i=1时，二叉树只有一个结点，结论成立。 设当i=k时结
6、论成立，则当i=k+1时，因为每个结点最多只有两个孩子，所以，第k+1层上至多有 2*2k-1 =2k 个结点，性质成立。,南京邮电大学计算机学院 陈慧南 2006年9月,性质5.2 高度为h的二叉树上至多有2h 1个结点。,证明：当h=0时，二叉树为空二叉树。当h0时，利用性质51，高度为h的二叉树中结点的总数最多为：,南京邮电大学计算机学院 陈慧南 2006年9月,性质5.3 包含n个元素的二叉树的高度至少为log2 (n+1),证明：由性质2，高度为h的二叉树最多有2h 1个结点，因而n2h 1, 则有hlog2(n+1)。因h是整数，所以h log2 (n+1)。,南京邮电大学计算机学
7、院 陈慧南 2006年9月,性质5.4 任意一棵二叉树中，若叶结点的个数为n0，度为2的结点的个数为n2，则必有n0=n2+1。,证明：设二叉树的结点总数为n，则 n=n0+n1+n2 孩子数为 n-1=n1+2n2， 因此， n0=n2+1,南京邮电大学计算机学院 陈慧南 2006年9月,定义5.4 高度为h的二叉树恰好有2h 1个结点时称为满二叉树 。 定义5.5 一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树 。 定义5.6 扩充二叉树 也称2树，扩充二叉树中除叶子结点外，其余结点都必须有两个孩子。,南京邮电大学计算
8、机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,性质5.5 具有n个结点的完全二叉树的高度为log2 (n+1)。,证明：设完全二叉树的高度为h，则除最下层外，前h-1层形成满二叉树，总共有2h-1 1个结点；而最下层，即第h层的结点个数最多不超过2h-1个。因此有 2h-11n2h1 移项得 2h-1n+12h 取对数 h-1log2(n+1) h log2(n+1) hlog2(n+1)+1 所以， h = log2 (n+1),南京邮电大学计算机学院 陈慧南 2006年9月,性质5.6 假定对一棵有n个结点的完全二叉树中的结点，按从上到下、从左到右的顺序，
9、从0到n-1编号，设树中某个结点的序号为i，0i0，则该结点的双亲的序号为 (i-1)/2；,南京邮电大学计算机学院 陈慧南 2006年9月,（3）若2i+1n，则该结点的左孩子的序号为2i+1，否则该结点无左孩子； (4)若2i+2n，则该结点的右孩子的序号为2i+2，否则该结点无右孩子。,南京邮电大学计算机学院 陈慧南 2006年9月,5.2.3 二叉树ADT,ADT BTree 数据： 二叉树是结点的有限集合，它或者为空集合，或 者由一个根结点和两棵互不相交的左、右子二叉树组成。 运算： Create(); 构造一棵空二叉树。 Destroy()：撤消一棵二叉树。 IsEmpty():若
10、二叉树为空，则返回true，否则返回false。 Clear():移去所有结点，成为空二叉树。,南京邮电大学计算机学院 陈慧南 2006年9月,Root(x): 若二叉树非空，则x有根的值，并返回true，否则返回false。 MakeTree(x, left, right): 构造一棵二叉树：根的值为x，以left和right为左右子树。 BreakTree(x, left, right):拆分二叉树为三部分：x为根的值，left和right分别为原树的左、右子树,南京邮电大学计算机学院 陈慧南 2006年9月,PreOrder(Visit):使用函数Visit访问结点, 先序遍历二叉树。
11、InOrder(Visit):使用函数Visit访问结点, 中序遍历二叉树。 PostOrder(Visit):使用函数Visit访问结点, 后序遍历二叉树。 ,南京邮电大学计算机学院 陈慧南 2006年9月,5.2.4 二叉树的存储表示,完全二叉树的顺序表示,南京邮电大学计算机学院 陈慧南 2006年9月,二叉树的链接表示(二叉链表),共有n-1个指针域非空,恰有n+1个空指针域。,南京邮电大学计算机学院 陈慧南 2006年9月,5.2.5 二叉树类,程序5.1 二叉树结点类 template struct BTNode BTNode() lChild=rChild=NULL; BTNode
12、(const T ,南京邮电大学计算机学院 陈慧南 2006年9月,BTNode(const T ,南京邮电大学计算机学院 陈慧南 2006年9月,T element; BTNode* lChild, *rChild; ;,南京邮电大学计算机学院 陈慧南 2006年9月,程序5.2二叉树类 template class BinaryTree public: BinaryTree()root=NULL; BinaryTree()Clear(); bool IsEmpty()const; void Clear();,南京邮电大学计算机学院 陈慧南 2006年9月,bool Root(T ,南京邮电
13、大学计算机学院 陈慧南 2006年9月,protected: BTNode* root; private: void Clear(BTNode* t); void PreOrder(void (*Visit)(T,南京邮电大学计算机学院 陈慧南 2006年9月,5.2.6 实现二叉树基本运算,程序5.3 部分二叉树运算 template bool BinaryTree:Root(T ,南京邮电大学计算机学院 陈慧南 2006年9月,template void BinaryTree:MakeTree(const T ,南京邮电大学计算机学院 陈慧南 2006年9月,template void B
14、inaryTree:BreakTree(T ,南京邮电大学计算机学院 陈慧南 2006年9月,void main(void) BinaryTreea,b,x,y,z; y.MakeTree(E,a,b); z.MakeTree(F,a,b); x.MakeTree(C,y,z); y.MakeTree(D,a,b); z.MakeTree(B,y,x); z.PreOrder(Visit); z.BreakTree(e,y,x); x.PreOrder(Visit); y.PreOrder(Visit); ,南京邮电大学计算机学院 陈慧南 2006年9月,5.3 二叉树遍历,南京邮电大学计算机
15、学院 陈慧南 2006年9月,5.3.1 二叉树遍历算法,遍历一个有限的结点集合，意味着对该集合中的每个结点访问且仅访问一次。,南京邮电大学计算机学院 陈慧南 2006年9月,先序遍历（VLR） 若二叉树为空，则空操作； 否则 （a）访问根结点； （b）先序遍历左子树； （c）先序遍历右子树。,先序遍历结点次序：,B,D,C,E,F,A,南京邮电大学计算机学院 陈慧南 2006年9月,中序遍历（LVR） 若二叉树为空，则空操作； 否则 （a）中序遍历左子树； （b）访问根结点； （c）中序遍历右子树,中序遍历结点次序：,D,A,E,C,F,B,南京邮电大学计算机学院 陈慧南 2006年9月,后序遍历（LRV） 若二叉树为空，则空操作； 否则 （a）后序遍历左子树； （b）后序遍历右子树； （c）访问根结点。,后序遍历结点次序：,B,E,F,C,A,D,南京邮电大学计算机学院 陈慧南 2006年9月,先序：,中序：,后序：,A,D,E,H,F,J,G,B,C,K,H,E,E,F,G,D,A,B,K,C,H,J,G,F,E,D,K,C,B,A,南京邮电大学计算机学院 陈慧南 2006年9月,层次遍历 二叉树还可以按层次遍历。二叉树的层次遍历为：首先访问第一层上的结点，再访问第二层上的
