72二叉树概念和性质 72.1二叉树的概念 二又树:二叉树也称为二次树或二分树它是有限的结点 集合这个集合或者是空或者由一个根结点和两棵互不相 交的称为左子树和右子树的二叉树组成。 特点每个结点至多只有两颗子树,且子树有左右之分, 其次序不能颠倒。 二又树是度为2的有序树? 二叉树的五种基本形态: A R T R T 空二又树(b)单结点的()根和 (d根和(e)根和左 左子树右子树右子树
7.2.1 二叉树的概念 二叉树：二叉树也称为二次树或二分树,它是有限的结点 集合,这个集合或者是空,或者由一个根结点和两棵互不相 交的称为左子树和右子树的二叉树组成。 特点:每个结点至多只有两颗子树，且子树有左右之分， 其次序不能颠倒。 7.2 二叉树概念和性质 (a) 空二叉树 A (b)单结点的 二叉树 A L_T (c)根和 左子树 A R_T (d)根和 右子树 A L_T R_T (e)根和左 右子树 二叉树的五种基本形态： 二叉树是度为2的有序树？
两类特弹的二叉树 满二叉树: 该二叉数中所有分支结点都有左孩子结点和右孩子结点 并且叶子结点都集中在二叉树的最下一层。 特点:每一层上的结点数都是最大结点数,即211 深度为k且有2k-1个结点的二叉树。 层次:1结点数:1 2-3-4 深度为4的满二叉树。 22
22 ➢ 满二叉树： 深度为4的满二叉树。 层次：1 结点数：1 2 2 3 4 4 8 特点：每一层上的结点数都是最大结点数，即2i-1 。 深度为k且有2k-1个结点的二叉树。 该二叉数中所有分支结点都有左孩子结点和右孩子结点， 并且叶子结点都集中在二叉树的最下一层。 两类特殊的二叉树
,二叉树结点的编号方法 根为1按照层数从小到大, 同一层从左到右的次序连续编号2 3 8(9④10①11(12①314①15 2 3 不是,因为编号为7的 结点是分支结点但无 8(9)(10(11(12①13)14 右孩子结点所以此 叉树不是满二叉树! 还是满二叉树吗?
1 2 4 8 9 5 10 3 6 7 11 12 13 14 15 满二叉树结点的编号方法: 根为1,按照层数从小到大, 同一层从左到右的次序连续编号 1 2 4 8 9 5 10 3 6 7 11 12 13 14 还是满二叉树吗？ 不是，因为编号为7的 结点是分支结点,但无 右孩子结点,所以此二 叉树不是满二叉树！
3 6(不是,因为编号为7 (8)(9)①0(11①12)13 的结点是叶子结点 但没有位于最下 是满二叉树吗? 层所以此二叉树不 是满二叉树! 24
24 1 2 4 8 9 5 10 3 6 7 11 12 13 是满二叉树吗？ 不是，因为编号为7 的结点是叶子结点, 但没有位于最下一 层,所以此二叉树不 是满二叉树！
完全二叉树: 深度为k有n个结点的二叉树,当且仅当其每一 个结点都与深度为k的满二叉树中编号从1至n的 结点一一对应位置对应)时,称之为完全二叉树。 3 3 89(10①112 8)(9⑩0①①2 25
25 ➢完全二叉树： 深度为k有n个结点的二叉树，当且仅当其每一 个结点都与深度为k的满二叉树中编号从1至n的 结点一一对应(位置对应）时，称之为完全二叉树。 1 2 4 8 9 5 10 3 6 7 11 12 1 2 4 8 5 9 3 6 7 10 11 12