数据结构-第六章 树8.pptVIP

第六章 树和二叉树 熟练掌握树和二叉树的基本概念 掌握二叉树的基本性质 熟练掌握树的顺序存储结构和链表存储结构 熟练掌握二叉树的顺序存储结构和链表存储结构 ??**掌握二叉树各种遍历操作的实现方法 ?? 掌握哈夫曼树的有关概念及哈夫曼编码的实现方法 ??了解查找树的各种操作的实现方法 上机 P149 5.3-1 平时30% 期中20% 50% 第六章 树和二叉树 5.1 树的概念 5.1.1 树的定义 5.2 二叉树 5.2.1 二叉树的定义 5.2.4 二叉树的存储结构 5.3 二叉树遍历 5.4 二叉树其他运算 5.5 树的存储结构和运算 5.5.3 树的运算 5.1 树的概念 5.1.1 树的定义 树(tree)是树型结构的简称。它是一种重要的非线性数据结构。 树——或者是一棵空树，即不含有任何结点（元素），或者是一棵非空树，即至少含有一个结点。 在一棵非空树中，它有且仅有一个称作根(root)的结点，其余所有结点分属于m个(m≥0)互不相交的集合，每个集合又构成一棵树，称它为根结点的子树(subtree)，并且树的根结点是每棵子树根结点的前驱，相反，每棵子树的根结点是所在树的根结点的后继。显然，树是一种递归定义的数据结构。 图就是一棵树T，它由根结点A和两棵子树T1和T2所组成，T1和T2分别位于A结点的左下部和右下部，其中树根结点A是两棵子树的根结点B和C的前驱，相反B和C是A的后继； T1又由它的根结点B和三棵子树T11,T12和T13所组成，这三棵子树分别位于B结点的左下部、中下部和右下部，其中B结点是这三棵子树的根结点D、E和F的前驱，相反它们都是B的后继；T11和T13只含有根结点，不含有子树(或者说子树为空树)，不可再分；T12又由它的根结点E和两棵只含有根结点的子树所组成，每棵子树的根结点分别为H和I，E是H和I的前驱，而H和I均是E的后继；T2由它的根结点C和一棵子树所组成，该子树也只含有一个根结点G，不可再分。 若采用第一章介绍的二元组来描述一棵树，则为： Tree=(K,R) K={ki | 1≤i≤n, n≥0, ki∈ElemType} 其中n为树中结点数，n=0则为空树，n0则为非空树。对于一棵非空树，关系R应满足下列条件： (1) 有且仅有一个结点没有前驱，该结点被称为树的根； (2) 除树根结点外，其余每个结点有且仅有一个前驱结点； (3) 包括树根结点在内的每个结点，可以有任意多个(含0个)后继。 对于图所示的树T，若采用二元组表示，则结点的集合K和K上二元关系R分别为： K={A,B,C,D,E,F,G,H,I} R={A,B,A,C,B,D,B,E,B,F,C,G,E,H,E,I} 5.1.2 树的表示 树的表示方法有多种。图5-1和5-2中的树形表示法是其中的一种，也是最常用的一种，图5-1和5-2中的结点是从上向下展开的，有时也需要树中的结点按从左向右展开。在树形表示法中，结点之间的关系是通过连线表示的，虽然每条连线上都不带有箭头(即方向)，但它并不是无向的，而是有向的，其方向隐含为从上向下或从左向右，即连线的上方或左边结点是下方或右边结点的前驱，下方或右边结点是上方或左边结点的后继。 树的另一种表示法是二元组表示法。除这两种之外，通常还使用广义表表示法，即每棵树的根作为由子树构成的表的名字而放在表的前面，图5-1树T的广义表表示为： A(B(D,E(H,I),F),C(G)) 5.1.3 树的基本术语 1. 结点的度和树的度 2. 分支结点和叶子结点 3. 孩子结点、双亲结点和兄弟结点 4. 结点的层数和树的深度 5. 有序树和无序树 6. 森林 结点 数据元素的内容及其指向其子树根的分支统称为结点。 结点的度 结点的分支数。 终端结点（叶子） 度为0的结点。 非终端结点(分支) 度不为0的结点。 结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推。 树的度 树中所有结点度的最大值。 树的深度 树中所有结点层次的最大值。 有序树、无序树 如果树中每棵子树从左向右的排列拥