树的存储 2链接存储--多重链表 ◆树的节点对应于链表的链点 ◆树节点间的分支关系用链点间的指针描述 ◆链点可能有多个指针--多重链表,每个指针描 述对应节点的一个分支关系 c有且仅有一个根链点 DATA c不同的指针指向不同的子树根链点 子树23 c一个子树有仅有一个根链点
树的存储 ◼ 2. 链接存储－－多重链表 ◆树的节点 对应于 链表的链点 ◆树节点间的分支关系用链点间的指针描述 ◆链点可能有多个指针－－多重链表，每个指针描 述对应节点的一个分支关系 有且仅有一个根链点 不同的指针指向不同的子树根链点 一个子树有仅有一个根链点 DATA 子树1 2 3
二叉树 353二叉树 1、定义 ◆二叉树是结点的有限集,或为空,或由根的左、 右子树组成,左右子树又分别是符合定义的二叉 树。仍然是递归定义。〉二叉树是树吗? ◆对比树的定义: c空二叉树树的定义中没有空树的概念 c不多于2个孩子树的节点可以有任意个子树 子树有左右之分无序树可不区分左右 树的其它定义适用于二叉树:根茎叶、度、路径
二叉树 ◼ 3.5.3 二叉树 ◼ 1、定义 ◆二叉树是结点的有限集，或为空，或由根的左、 右子树组成，左右子树又分别是符合定义的二叉 树。 ◆对比树的定义： 空二叉树 树的定义中没有空树的概念 不多于2个孩子 树的节点可以有任意个子树 子树有左右之分 无序树可不区分左右 ◆树的其它定义适用于二叉树：根茎叶、度、路径 仍然是递归定义。 二叉树是树吗？
二叉树 (4)二叉树的形态 空树无子树仅有左子树仅有右子树有左右子树
二叉树 ◼ （4）二叉树的形态 空树 无子树 仅有左子树 仅有右子树 有左右子树
二叉树的性质 2二叉树的性质 ◆(1)在二叉树的第层上最多有2个结点 c第层的结点数最多是第i-1层的两倍 ◆(2)深度为k的二叉树最多有2k-1个结点 ◆(3)叶结点数比具有两个孩子的结点数多1个
二叉树的性质 ◼ 2. 二叉树的性质 ◆（1）在二叉树的第i层上最多有2 i-1个结点 第i层的结点数最多是第i-1层的两倍 ◆（2）深度为k的二叉树最多有2 k - 1个结点 ◆（3）叶结点数比具有两个孩子的结点数多 1个
二叉树的性质 (3)叶结点数比具有两个孩子的结点数多1个 设n为叶结点个数 n为具有一个孩子的分支结点个数, n2为具有两个孩子的分支结点个数, n为结点总个数 结论:n=n2+1; 条件1、n=n+n1+n2 条件2、n=分支的个数+1 设为分支的个数为B 条件3、B=2n2+n1 所以:2n2+n1+1=no+n1+n2
二叉树的性质 ◼ （3）叶结点数比具有两个孩子的结点数多1个 设n0为叶结点个数， n1为具有一个孩子的分支结点个数， n2为具有两个孩子的分支结点个数， n为结点总个数 结论： n0 = n2 + 1; 条件1、 n = n0 + n1 + n2 条件2、 n = 分支的个数 + 1 设为分支的个数为B 条件3、 B = 2 n2 + n1 所以： 2n2 + n1 + 1 = n0 + n1 + n2