《数据结构A》第5章.ppt

数据结构数据结构 Data Structures in C+南京邮电大学计算机学院南京邮电大学计算机学院 20062006年年9 9月月第第5 5章章 树树5 5.1.1树的基本概念树的基本概念5 5.2.2二叉树二叉树5 5.3.3二叉树的遍历二叉树的遍历5.45.4二二叉叉树树遍遍历历的的非非递递归归算算法法5 5.5.5树和森林树和森林5 5.6.6堆和优先权队列堆和优先权队列5 5.7.7哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码5 5.8.8并查集和等价关系并查集和等价关系南京邮电大学计算机学院南京邮电大学计算机学院 20062006年年9 9月月5.1 5.1 树的基本概念树的基本概念 树形结构是元素之间有着分层关系的结构，树形结构是元素之间有着分层关系的结构，它类似于自然界中的树。这是一类很重要的它类似于自然界中的树。这是一类很重要的非线性数据结构。非线性数据结构。一方面，计算机应用中，常常出现嵌套的一方面，计算机应用中，常常出现嵌套的数据，树结构提供了对该类数据的自然表示。数据，树结构提供了对该类数据的自然表示。另一方面利用树结构，我们可以有效地解决另一方面利用树结构，我们可以有效地解决一些算法问题。一些算法问题。南京邮电大学计算机学院南京邮电大学计算机学院 20062006年年9 9月月图图5-1 5-1 西欧语言谱系图西欧语言谱系图原始印欧语原始印欧语古意大利语古意大利语日耳曼语日耳曼语西日耳曼语西日耳曼语拉丁语拉丁语西西班班牙牙语语法法语语意意大大利利语语希腊语希腊语北日耳曼语北日耳曼语冰冰岛岛语语瑞瑞典典语语挪挪威威语语英英语语荷荷兰兰语语德德语语古希腊语古希腊语南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南5.1.1树的定义树的定义 定义定义定义定义5.15.1树树是包括是包括n n个结点的有限个结点的有限非空集合非空集合D D，R R是是D D中元素的序偶中元素的序偶的集合，的集合，R R满足以下特性：满足以下特性：（1 1）有有且且仅仅有有一一个个结结点点r r D D，不不存存在在任任何何结结点点v v D D，v v r r，使使得得 R R，称，称r r为树的为树的根根根根 ；（2 2）除除根根r r以以外外的的所所有有结结点点u u D D，都都有有且且仅仅有有一一个个结结点点v v D D，v v u u，使得，使得 R R。这样定义的树也称这样定义的树也称有根树有根树，简称，简称树树。南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南定义定义5.2树树是包括是包括n n个结点的有限非空集合个结点的有限非空集合T T，其中，一个特定的结点，其中，一个特定的结点r r称为称为根根，其余结，其余结点点 T-rT-r划分成划分成m m（m m 0 0）个互不相交的子）个互不相交的子集集T1,T2,Tm，其中，每个子集都是树，其中，每个子集都是树，被称为树根被称为树根r r的的子树子树。南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南5.1.2 基本术语基本术语 树树中中元元素素常常称称为为结结点点 。根根和和它它的的子子树树根根（如如果果存存在在）之之间间形形成成一一条条边边 。如如果果从从某某个个结结点点沿沿着着树树中中的的边边可可到到达达另另一一个个结结点点，则则称称这这两两个个结结点点间间存存在在一一条条路路径径 。南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南 若若一一个个结结点点有有子子树树，那那么么该该结结点点称称为为子子树树根根的的双双亲亲，子子树树的的根根是是该该结结点点的的孩孩子子。有有相相同同双双亲亲的的结结点点互互为为兄兄弟弟。一一个个结结点点的的所所有有子子树树上上的的任任何何结结点点都都是是该该结结点点的的后后裔裔。从从根根结结点点到到某某个个结结点点路路径径上上的的所所有有结点都是该结点的结点都是该结点的祖先祖先。南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南一一个个结结点点拥拥有有的的子子树树数数称称为为该该结结点点的的度度。度度为为零零的的结结点点称称为为叶叶子子，其其余余结结点点称称为为分分支支结结点点。树树中中结结点点的最大的度称为的最大的度称为树的度。树的度。树树是是层层次次结结构构的的，规规定定根根结结点点的的层层次次为为1 1，其其结结点点的的层层次次等等于于其其双双亲亲结结点点的的层层次次加加1 1。树树中中结结点点的的最最大层次称为该大层次称为该树的高度树的高度。南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南如如果果树树中中结结点点的的各各子子树树之之间间的的次次序序是是不不重重要要的的，可可以以交交换换位位置置，这这样样的的树树称称为为无无序序树树。也也就就是是我我们们通通常常所所说说的的树树。如如果果将将树树中中结结点点的的各各棵棵子子树树看看成成是是从从左左到到右右有有次次序序的的，则则称称该该树树为为有有序序树树。从从左左到到右右，可可分分别别称称这这些些子子树树为为第第一一子子树树，第第二二子子树等等。树等等。森林森林是是树树的集合。的集合。果园果园或称或称有序森林有序森林是是有序树有序树的有序集合。的有序集合。南京邮电大学计算机学院南京邮电大学计算机学院 陈慧南陈慧南