第六章树和二叉树PPT课件.ppt

第六章树和二叉树 树的定义与基本操作二叉树树和森林哈夫曼树与哈夫曼编码 1 6 1树的定义与基本操作 树的定义 n n 0 个结点的有限集 当n 0时 称为空树 任意一棵非空树中 有且仅有一个特定的称为根 Root 的结点 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 并且称为根的子树 SubTree 2 根 子树 3 树的基本术语 结点的度 结点所拥有的子树的个数 树的度 树中各结点度的最大值 叶子 度为0的结点 也称为终端结点 分支结点 度不为0的结点 也称为非终端结点 孩子 树中某结点子树的根结点称为该结点的孩子结点 兄弟 具有同一个双亲的孩子结点互称为兄弟 路径 若树中存在一个结点序列n1 n2 nk使得结点ni是ni 1的双亲 1 i k 则把n1 n2 nk称为一条由n1至nk的路径 路径上经过的边的数目 等于k 1 称为路径长度 双亲 与孩子结点相对应 4 层数 根结点的层数为1 对其余任何结点 若某结点在第i层 则其孩子结点在第i 1层 堂兄弟 双亲在同一层的结点 树的深度 树中结点的最大层数 也称高度 有序树 无序树 如果一棵树中结点的各子树从左到右是有次序的 称这棵树为有序树 反之 称为无序树 森林 m m 0 棵互不相交的树的集合 祖先 从根到该结点所经分支上的所有结点 子孙 以某结点为根的子树中的任一结点都称为该结点的子孙 5 K L F G M I J 结点B的孩子 E F 结点B C D为兄弟结点K L为兄弟 树的度 树的深度 结点F G为堂兄弟结点A是结点F G的祖先 结点A的度 3 结点B的度 结点M的度 2 0 结点A的孩子 B C D 3 结点A的层次 1 结点M的层次 4 叶子 结点I的双亲 D 结点L的双亲 E 4 6 树的逻辑特征 1 树中任一结点都可以有零个或多个直接后继结点 但至多只能有一个直接前趋结点 即双亲结点 2 树中只有根结点无前趋 它是开始结点 叶子结点无后继 它们是终端结点 3 祖先与子孙的关系是父子关系的延伸 它定义了树中各结点之间的纵向次序 4 在有序树中 同一组兄弟结点从左到右有长幼之分 它定义了树中各结点之间的横向次序 7 树的抽象数据类型 数据对象D 一个集合 该集合中的所有元素具有相同的特性 数据关系R 若D为空集 则为空树 若D中仅含有一个数据元素 则R为空集 否则R H H是如下的二元关系 1 在D中存在唯一的称为根的数据元素root 它在关系H下无前驱 2 在D root 则存在D root 的一个划分D1 D2 Dm m 0 对任意j k 1 j k m 有Di Dj 且对任意的i 1 i m 存在唯一的数据元素xi Di H 3 对应于D root 的划分 H 有唯一的一个划分H1 H2 Hm m 0 对任意i 1 i m Hi是Di上的二元关系 Di H 是一棵符合本定义的树 称为根root的子树 8 基本操作 1 InitTree T 将T初始化为一棵空树 2 DestoryTree T 销毁树T 3 CreateTree T definition 创建树T 4 TreeEmpty T 若T为空 则返回TRUE 否则返回FALSE 5 Root T 返回树T的根 6 Parent T x 树T存在 x是T中的某个结点 若x为非根结点 则返回它的双亲 否则返回 空 7 LeftChild T x 树T存在 x是T中的某个结点 若x为非叶子结点 则返回它的最左孩子结点 否则返回 空 8 RightSibling T x 树T存在 x是T中的某个结点 若x有右兄弟 则返回x的右兄弟结点 否则返回 空 9 TreeDepth T 求树的深度 若T存在 返回树T的深度 9 10 InsertChild T p i x 树T存在 p指向T中某个结点 非空树x与T不相交 将x插入T中 做p所指向结点的第i棵子树 11 DeleteChild T p i 树Tree存在 p指向T中某个结点 1 i d d为p所指向结点的度 删除T中p所指向结点的第i棵子树 12 TraverseTree T 树T存在 按照某种次序对树T的每个结点进行一次且至多一次的遍历 10 6 2二叉树 定义 二叉树是n n 0 个结点的有限集 它或为空树 n 0 或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点每个结点至多有二棵子树 即不存在度大于2的结点 二叉树的子树有左 右之分 且其次序不能任意颠倒 基本形态 11 二叉树的基本性质 性质1 证明 用归纳法证明 i 1时 只有一个根结点 是正确的 假设对所有j 1 j i 命题成立 即第j层上至多有个结点 则可以证明j i时命题成立 由归纳法假设 第i 1层至多有个结点又二叉树每个结点的度至多为2 第i层上最大结点数是第i 1层上的最大结点数的2倍 即 故命题得证 在二叉树的第i层上至多有2i 1个结点 i 1 12 性质2 深度为k的二叉树至多有个结点 k 1 证明 由性质1 可得深度为k的二叉树最大结点数是 13 性质3 对任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1 证明 设二叉树中结点总数为n n1为二叉树中度为1的结点总数 因为二叉树中所有结点的度小于等于2 所以有n n0 n1 n2 设二叉树中分支数目为B 因为除根结点外 每个结点均对应一个进入它的分支 所以有 n B 1 又因为二叉树中的分支都是由度为1和度为2的结点发出 所以分支数目为 B n1 2n2 整理上述两式可得到 n B 1 n1 2n2 1 将n n0 n1 n2代入上式得出n0 n1 n2 n1 2n2 1 整理后得n0 n2 1 14 满二叉树与完全二叉树 满二叉树 一棵深度为k且有2k 1个结点的二叉树 1 每一层上的结点数都达到最大值 2 满二叉树中不存在度数为1的结点 每个分支结点均有两棵高度相同的子树 且叶子结点都在最下一层 完全二叉树 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2 并且最下一层上的结点都集中在该层最左边的若干位置上 则此二叉树称为完全二叉树 1 满二叉树是完全二叉树 完全二叉树不一定是满二叉树 2 在满二叉树的最下一层上 从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树 3 在完全二叉树中 若某个结点没有左孩子 则它一定没有右孩子 即该结点必是叶结点 可以对满二叉树的结点进行连续编号 约定编号从根结点起 自上而下 自左而右 由此 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时 称之为完全二叉树 15 满二叉树 完全二叉树 哪些是完全二叉树 16 性质4 具有n个结点的完全二叉树的深度为 log2n 1 性质5 如果对一棵有n个结点的完全二叉树的结点按层序编号 则对任一结点i 1 i n 有 1 如果i 1 则结点i是二叉树的根 无双亲 如果i 1 则其双亲是 i 2 2 如果2i n 则结点i无左孩子 否则 则其左孩子是2i 3 如果2i 1 n 则结点i无右孩子 否则 则其右孩子是2i 1 17 二叉树的存储结构 顺序存储 顺序存储结构 用一组地址连续的存储单元依次自上而下 自左至右来存放二叉树的数据元素 二叉树的顺序存储结构 18 对于一般的二叉树 我们按照完全二叉树的形式来存储 就会造成空间的浪费 单支树就是一个极端情况 特点 结点间关系蕴含在其存储位置中 浪费空间 适于存满二叉树和完全二叉树 19 二叉树的存储结构 链式存储 链式存储结构 对于任意的二叉树来说 每个结点至多只有两个孩子 一个双亲结点 我们可以设计每个结点至少包括三个域 数据域 左孩子域和右孩子域 二叉链表 含两个指针域的结点结构 lChilddataparentrChild 含三个指针域的结点结构 三叉链表 20 A A A B B B C C C D D D F F F E E E root root