《《数据结构A》第5章.ppt》由会员分享，可在线阅读，更多相关《《数据结构A》第5章.ppt（10页珍藏版）》请在三一办公上搜索。
1、南京邮电大学计算机学院 2006年9月,数据结构,Data Structures in C+,南京邮电大学计算机学院 2006年9月,第5章 树,5.1 树的基本概念5.2 二叉树5.3 二叉树的遍历5.4 二叉树遍历的非递归算法5.5 树和森林5.6 堆和优先权队列5.7 哈夫曼树和哈夫曼编码5.8 并查集和等价关系,南京邮电大学计算机学院 2006年9月,5.1 树的基本概念,树形结构是元素之间有着分层关系的结构，它类似于自然界中的树。这是一类很重要的非线性数据结构。一方面，计算机应用中，常常出现嵌套的数据，树结构提供了对该类数据的自然表示。另一方面利用树结构，我们可以有效地解决一些算法问
2、题。,南京邮电大学计算机学院 2006年9月2006年9月,南京邮电大学计算机学院 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月2006年9月,定义5.2 树是包括n个结点的有限非空集合T，其中，一个特定的结点r称为根，其余结点 T-r划分成m（m0）个互不相交的子集T1,T2,Tm，
3、其中，每个子集都是树，被称为树根r的子树。,南京邮电大学计算机学院 2006年9月2006年9月,5.1.2 基本术语,树中元素常称为结点。根和它的子树根（如果存在）之间形成一条边。如果从某个结点沿着树中的边可到达另一个结点，则称这两个结点间存在一条路径。,南京邮电大学计算机学院 2006年9月2006年9月,若一个结点有子树，那么该结点称为子树根的双亲，子树的根是该结点的孩子。有相同双亲的结点互为兄弟。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点路径上的所有结点都是该结点的祖先。,南京邮电大学计算机学院 2006年9月2006年9月,一个结点拥有的子树数称为该结点的度。度为零的结点称为叶子，其余结点称为分支结点。树中结点的最大的度称为树的度。树是层次结构的，规定根结点的层次为1，其结点的层次等于其双亲结点的层次加1。树中结点的最大层次称为该树的高度。,南京邮电大学计算机学院 2006年9月2006年9月,如果树中结点的各子树之间的次序是不重要的，可以交换位置，这样的树称为无序树。也就是我们通常所说的树。如果将树中结点的各棵子树看成是从左到右有次序的，则称该树为有序树。从左到右，可分别称这些子树为第一子树，第二子树等等。,森林是树的集合。果园或称有序森林是有序树的有序集合。,
