第6章 - 树和二叉树(4课时-前3节).ppt

Page * 谢谢大家！ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 《数据结构》 李 凯 2013年11月 第六章 树 Page * 6.1 树定义和运算 6.2 二叉树 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树 内容 设置 Page * 6.1 树定义与运算 定义 定义：树(tree)是n(n≥0)个结点的有限集T，当n=0时称为空树。在任一非空树中： ⑴有且仅有一个特定的结点，称为树的根(root) ⑵其余结点可分为m(m≥0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。 特点：结点之间具有层次关系；某个元素最多只与上一层的一个元素有直接关系，而可以与其下一层的多个元素有直接关系。与线性表相比，树中每个结点至多有一个前趋(父结点)，但可以有多个后继结点(孩子结点)。 说明：树的定义是一个递归定义。 Page * 6.1 树定义与运算 定义 A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树 Page * 6.1 树定义与运算 表示 方法 树的表示方法：树形表示法；凹入表表示法；嵌套集合表示法；广义表表示法 Page * 6.1 树定义与运算 基本 术语 ⑴ 结点(node)：表示树中的元素，包括数据项及若干指向其子树的分支 ⑵ 结点的度(degree)：结点拥有的子树数 ⑶ 叶子(leaf)：度为0的结点。否则称为分支结点。 ⑷ 孩子(child)：结点子树的根称为该结点的孩子 ⑸ 双亲(parents)：孩子结点的上层结点叫该结点的~ ⑹ 兄弟(sibling)：同一双亲的孩子 Page * 6.1 树定义与运算 基本 术语 ⑺树的度：一棵树中最大的结点度数 ⑻结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层…… ⑼深度(depth)：树中结点的最大层次数 ⑽森林(forest)：m(m≥0)棵互不相交的树的集合 ⑾有序树：树中结点的各子树看成是从左到右有次序的，不能互换。反之，称为无序树。 Page * 6.1 树定义与运算 基本 术语 Page * 6.1 树定义与运算 基本 运算 ⑴ 初始化树Tree_Initial (T)： 建立树或森林T的初始结构。 ⑵ 插入子树Tree_Insert(T,S)： 将以S为根的树作为第一个子树插入到树T中。 ⑶ 插入兄弟结点Tree_SiblingInsert(T,S)： 将以S为根的树作为T的兄弟子树插入到树中。 ⑷ 查询根结点Tree_Root(T)： 查询结点T所在树的根结点。 Page * 6.1 线性表定义与运算 基本 运算 ⑸ 查询父结点Tree_Father(T)： 查询结点T的父结点。 ⑹ 查询孩子结点Tree_Child(T)： 查询结点T的所有或某一个孩子结点。 ⑺ 查询兄弟结点Tree_Sibling(T)： 查询结点T的所有或某一个兄弟结点。 Page * 6.2 二叉树 概念 定义：二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 特点：⑴ 每个结点至多有二棵子树(即不存在度大于2的结点)；⑵ 二叉树的子树有左、右之分，且其次序不能任意颠倒。 基本形态： A 只有根结点 的二叉树 ? 空二叉树 A B 右子树为空 A B 左子树为空 A B C 左、右子树 均非空 Page * 6.2 二叉树 性质 性质1：在二叉树的第i层上至多有2i-1个结点(i ≥1)。 性质2：深度为k的二叉树至多有 2k-1个结点(k≥1)。 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明：设n1为二叉树T中度为1的结点数。其结点总数n=n0+n1+n2。又二叉树中，除根结点外，其余结点都只有一个分支进入。设B为分支总数，则n=B+1 又，分支由度为1和度为2的结点射出，B=n1+2n2。 于是，n=B+1=n1+2n2+1=n0+n1+n2，从而n0=n2+1。 Page * 6.2 二叉树 性质 定义：一棵深度为k 且有2k-1个结点的二叉树称为满二叉树。 显然，满二叉树每一层上的结点数都是最大结点数。 定义：完全二叉树是指在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。 完全二叉树的特点: 叶子结点只可能在层次最大的两层上出现。对任一结点，若其右分支下子孙的最大层次为n，则其左分支下子孙的最大层次必为n或n+1 Page * 6.2 二叉树 性质 完全二叉树： Page * 6.