算法与数据结构课件-第5章 树与二叉树.ppt

树例与特征 社会的组织机构 家族的族谱 计算机中的目录组织 描述层次结构，是一种一对多的逻辑关系 第5章 树与二叉树 5.1 树的概念与基本操作 5.1.1 树的定义及相关术语 树(Tree)是n(n=0)个结点构成的有限集合； n=0时称为空树； 非空树满足的条件： 有且仅有一个称为根（Root）的结点； n1时，其余结点可分为m(m0)个互不相交的有限集合T1…Tm,其中每个集合又是一棵树，称为子树。 树的定义 2. 相关术语 结点的度(Degree) ：结点拥有的子树的数目； 叶子（终端结点Leaf ）：度为0的结点； 分支结点（非终端结点）：度不为0的结点；除根结点之外的分支结点统称为内部结点； 树的度：树内各结点的度的最大值； 孩子(Child)，双亲(Parent) ，兄弟(Sibling): 结点的子树的根称为 该结点的孩子；该结点 称为孩子的双亲； 同一个双亲的孩子 之间互称兄弟。 概 念 无序树：可以互换; 森林(Forest)：m(m≥0)棵互不相交的树的集合。 （1） Initiate（t）初始化一棵空树t。 （2） Root（x）求结点x所在树的根结点。 （3） Parent（t，x）求树t中结点x的双亲结点。 （4）Child（t，x，i）求树t中结点x的第i个孩子结点。 （5）RightSibling（t，x）求树t中结点x的第一个右边兄弟结点。 （6）Insert（t，x，i，s）把以s为根结点的树插入到树t中作为结点x的第i棵子树。 （7）Delete（t，x，i）在树t中删除结点x的第i棵子树。 （8）Traverse（t）是树的遍历操作 5.2 二叉树 5.2.1 二叉树的基本概念 二叉树(Binary Tree)： 或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树。 特征： 每个结点最多只有两棵子树 子树有左右之分， 其次序不能任意颠倒 二叉树也可以用递归的形式定义。 即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树； 当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 二叉树的五种形态 满二叉树（特殊形态的二叉树） 满二叉树： 所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上 每一层上的结点数都是最大结点数； 不存在度为1的结点。 可以对满二叉树的结点进行连续编号 编号方式为：从上到下，从左到右。 完全二叉树（特殊形态的二叉树） 完全二叉树： 深度为k，有n个结点的二叉树，对树中的结点进行编号，如果编号为i的结点都与满二叉树中编号为i的结点在二叉树中的位置相同，称为完全二叉树。 特征： 叶子结点只可能在层次最大的两层上出现 最下层的叶子结点集中在左部 任一结点，若其右子树的最大层次为k，则其左分支下的最大层次为k或k+1 5.2.2 二叉树的主要性质 1.一棵非空二叉树的第i层上最多有2i-1个结点(i?1)。 证明：i = 1, 只有根结点，显然成立 设i = k时成立，第k层最多有2k-1个结点 当i= k+1时，最多的结点个数： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1 2.一棵深度为i的二叉树中，最多有2i-1个结点。 证明：只有每层的结点数达到最大时，其树的结点 数为最多。 由性质1，二叉树的结点个数为： 20 +21 +22 +……+2k-1 =2k-1 二叉树的性质 3.对于一棵非空的二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有n0 = n2 +1; 证明： 设n1为二叉树中度为1的结点数，则总结点数： n = n0 + n1 + n2 另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则 B = n1 + 2 * n2 = n - 1； n1 + 2 * n2 = n0 + n1 + n2 – 1; ∴ n0 = n2 + 1; 练 习 1.设一棵完全二叉树共有700个结点，则该二叉树有几个叶子结点，有几个度为1的结点？ 2.设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中有几个叶子结点。 完全二叉树的特性 1.具有n个结点的完全二叉树的深度为 k = ?log2n?+1 其中， ?x? 表示不大于x的最大整数，如 ? 6.9 ?