数据结构第六章树南京工程学院通信工程学院.pptVIP

前面我们学习的线性数据结构，每个元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样简单，例如在编译程序中，用树表示源程序的语法结构。 本章学习一种非线性数据结构——树，数据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继。;树的概念和基本术语 二叉树 二叉树遍历 线索二叉树 树与森林 霍夫曼树 ;6.1树的概念和基本术语;;树的基本术语 树的结点：包含一个数据元素及若干指向子树的分支； 孩子结点：结点的子树的根称为该结点的孩子 双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；; 树的高度：树中结点的最大层次.结点的度：结点子树的个数树的度： 树内各结点的度的最大值。叶子结点：也叫终端结点，是度为0的结点；分枝结点：度不为0的结点；有序树：子树有序的树，（子树不能互换）如：家族树；无序树：不考虑子树的顺序； ;任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林;路径：树中的k 个结点n1,n2，… ，nk，满足ni 是ni + 1 的双亲，n1到nk有一条路径 路径长度：分支数＝路径上结点个数一1 ;对比树型结构和线性结构的结构特点;树的常见表示方法;2 、集合表示法： 根据树的集合定义，写出集合划分。 3 、文氏图表示法：集合表示的一种直观表示，用图表示集合。;4 、目录表示法：将一棵树描述为一本书，书--章--节--小节 ;5 、广义表表示法： 将一棵树描述为一个广义表，子树就对应子表。;基本操作;TreeDepth（T） 初始条件：树T存在。 操作结果：返回T的深度。 Root（T） 初始条件：树T存在。 操作结果：返回T的根。 Value（T, Cur_e） 初始条件：树T存在，cur＿e是T中某 个结点。 操作结果：返回cur＿e的值。 Assign（T，cur_e，value） 初始条件：树T存在，cur＿e是T中某个结点。 操作结果：结点cur_e赋值 为value。 Parent（T，cur＿e） 初始条件：树T存在，cur＿e是T中某个结点??? 操作结果：若cur＿e是T的非根结点，则返回它的双亲，否则函数值为“空”。 Rightsibling（T，cur＿e） 初始条件：树T存在，cur＿e是T中某个结点 操作结果：若cur＿e有右兄弟，则返回它的右兄弟，否则函数值为“空”。 ; LeftChild（T，cur＿e） 初始条件：树T存在，cur＿e是T中某个结点。 操作结果：若cur＿e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。 InsertChild（＆T，＆p，i，c）； 初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度＋1，非空树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。 DeleteChild（＆T，＆p，i）； 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree（T，visit（））； 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit() 一次且至多一次.一旦visit（）失败，则操作失败;6.2 二叉树 6.2.1 二叉树的概念 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构;;二叉树的五种基本形态：;应用举例 例 可以用二叉树表示表达式;性质1 在二叉树的第 i 层上至多有 2i －1个结点。(i ? 1) [证明用归纳法] 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，ij?1，命题成立，即第j层上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i －2个结点。 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2* 2i －2= 2 i-1。;性质2 深度为 k 的二叉树至多有 2 k-1个结点(k ? 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 ;性质3 对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0＝n2＋1. 证明：若度为1的结点有 n1 个，总结点个数为 n，总边数为