数据结构第六节(公共邮箱).ppt

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和有哪些信誉好的足球投注网站二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.1 树的定义和基本术语 树的定义 树是由 n (n ? 0) 个结点组成的有限集合.如果n=0,称为空树;如果n0，则称为非空树。在一棵非空树中： ? 有且仅有一个称为根(Root)的结点，它只有直接后继，但没有直接前驱； ? 当n1时，除根以外的其它结点可划分为m (m ?0) 个互不相交的有限集合T1, T2, …, Tm，每个集合本身又是一棵树，并且称之为根的子树(Sub Tree)。 树的抽象数据类型定义： ADT Tree{ 数据对象D： 数据关系R： 基本操作： } ADT Tree 基本术语 结点: 数据元素+ 若干指向子树的分支 结点的度: 分支的个数 树的度: 树中所有结点的度的最大值 叶子结点: 度为零的结点 分支结点: 度大于零的结点 从根到结点的路径:由从根到该结点所经分支和结点构成。 孩子结点 双亲结点 兄弟结点 祖先 子孙 有序树：树中结点的子树从左到右是有次序的。 无序树： 森林：是m（m≥0）棵互不相交的树的集合 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root被称为根结点，F被称为子树森林 基本操作 查找 插入 删除 查找（8） Root(T); Value(T, cur_e); Parent(T, cur_e); LeftChild(T, cur_e); RightSibling(T, cur_e); TreeEmpty(T); TreeDepth(T); TraverseTree(T, Visit()); 插入（4） InitTree(T); CreateTree(T, definition); Assign(T, cur_e, value); InsertChild(T, p, i, c); 在P结点下面插入一棵以c为根的子树，作为P结点的第 i 棵子树 删除（3） ClearTree( T ); DestroyTree( T ); DeleteChild( T, p, i ); 删除p结点的第i棵子树 树形结构和线性结构的比较 线性结构 树结构 第一个数据元素(无前驱) 根结点(无前驱) 最后一个数据元素(无后继) 多个叶子结点(无后继) 其它数据元素 树中其它结点 (一个前驱、一个后继) (一个前驱、多个后继) 树的表示法 P120 树型表示法 文氏图法 广义表法（嵌套括号） 凹入法 二叉树的五种基本形态： 二叉树的主要基本操作： 查找 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit()); 插入 InitBiTree(T); Assign(T, e, value);结点e赋值value。 CreateBiTree(T, definition); InsertChild(T, p, LR, c); 为结点P插入子树C，如果LR等于0，那么插入的子树C作为P的左子树，如果LR等于1，则插入的子树C作为P的右子树。 删除： ClearBiTree(T); DestroyBiTree(T); DeleteChild(T, p, LR); 二叉树的重要特性： 性质 1 ： 在二叉树的第 i 层上至多有2i-1个结点(i≥1) 性质 2 ： 深度为k的二叉树上至多含2k-1个结点（k≥1） 性质 3 ： 对任何一棵二叉树，若他含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0 = n2+1