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

南京邮电大学计算机学院2006年9月 数据结构 DataStructuresinC 南京邮电大学计算机学院2006年9月 第5章树 5 1树的基本概念5 2二叉树5 3二叉树的遍历5 4二叉树遍历的非递归算法5 5树和森林5 6堆和优先权队列5 7哈夫曼树和哈夫曼编码5 8并查集和等价关系 南京邮电大学计算机学院2006年9月 5 1树的基本概念 树形结构是元素之间有着分层关系的结构 它类似于自然界中的树 这是一类很重要的非线性数据结构 一方面 计算机应用中 常常出现嵌套的数据 树结构提供了对该类数据的自然表示 另一方面利用树结构 我们可以有效地解决一些算法问题 南京邮电大学计算机学院陈慧南2006年9月 南京邮电大学计算机学院陈慧南2006年9月 5 1 1树的定义 定义5 1树是包括n个结点的有限非空集合D R是D中元素的序偶的集合 R满足以下特性 1 有且仅有一个结点r D 不存在任何结点v D v r 使得 R 称r为树的根 2 除根r以外的所有结点u D 都有且仅有一个结点v D v u 使得 R 这样定义的树也称有根树 简称树 南京邮电大学计算机学院陈慧南2006年9月 定义5 2树是包括n个结点的有限非空集合T 其中 一个特定的结点r称为根 其余结点T r 划分成m m 0 个互不相交的子集T1 T2 Tm 其中 每个子集都是树 被称为树根r的子树 南京邮电大学计算机学院陈慧南2006年9月 5 1 2基本术语 树中元素常称为结点 根和它的子树根 如果存在 之间形成一条边 如果从某个结点沿着树中的边可到达另一个结点 则称这两个结点间存在一条路径 南京邮电大学计算机学院陈慧南2006年9月 若一个结点有子树 那么该结点称为子树根的双亲 子树的根是该结点的孩子 有相同双亲的结点互为兄弟 一个结点的所有子树上的任何结点都是该结点的后裔 从根结点到某个结点路径上的所有结点都是该结点的祖先 南京邮电大学计算机学院陈慧南2006年9月 一个结点拥有的子树数称为该结点的度 度为零的结点称为叶子 其余结点称为分支结点 树中结点的最大的度称为树的度 树是层次结构的 规定根结点的层次为1 其结点的层次等于其双亲结点的层次加1 树中结点的最大层次称为该树的高度 南京邮电大学计算机学院陈慧南2006年9月 如果树中结点的各子树之间的次序是不重要的 可以交换位置 这样的树称为无序树 也就是我们通常所说的树 如果将树中结点的各棵子树看成是从左到右有次序的 则称该树为有序树 从左到右 可分别称这些子树为第一子树 第二子树等等 森林是树的集合 果园或称有序森林是有序树的有序集合