4.1 树与二叉树　课件　2022—2023学年浙教版（2019）高中信息技术选修1

树与二叉树 选修一：数据结构 更多模板请关注：https://haosc.tukuppt.com 1 树 2 树形逻辑结构的应用 3 树的基本概念 树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足： 1）有且仅有一个特定的结点称为根的结点。 2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T , T ,…, T ，其中每个集合本身又是一棵树，并且称为根结点的子树。 4 树的基本概念 非空树的特点： 🎄有且仅有一个根节点ꢀ 🎄没有后继的结点称为“叶子结点”（或终端结点） 🎄有后继的结点称为“分支结点”（或非终端结点） 🎄除了根节点外，任何一个结点都有且仅有一个前驱 🎄每个结点可以有0个或多个后继。 5 树的基本概念 下列是否为树形结构？ 否，除根节点外，任何一个节点都有且仅有一个前驱 6 数的基本概念 属性： n个结点的树，有n-1条边 树的高度——总共多少层 结点的度——有几个孩子 树的度——各结点度的最大值 7 二叉树 8 二叉数的基本概念 二叉树是n（n≥0）个结点的有限集合： ① n = 0时，二叉树是一棵空树。。 ② 当n ≠ 0时，二叉树是由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。 9 二叉数的特点 ①每个结点至多只有两棵子树。 ②左右子树不能颠倒（二叉树是有序树） 10 二叉数的五种状态 11 特殊的二叉树—满二叉树 满二叉树：每一层的节点数都达到最大值 12 特殊的二叉树--完全二叉树 当且仅当其每个结点都与高度为h的满二叉树中的结点一一对应时，称为完全二叉树 特点： ①只有最后两层可能有叶子结点 ②最多只有一个度为1的结点 13 特殊的二叉树 不是完全二叉树 完全二叉树如果某结点只有一个孩子，一定是左孩子 该二叉树是完全二叉树吗？ 14 二叉数的常考性质 ①二叉树第i层至多有（i≥1） ②深度为k的二叉树多有（i≥1） 第 1 层：20 第 2 层：21 第 3 层：22 第 4 层：23 15 二叉数的常考性质 ③在任意一棵二叉树中，若度为2的节点数量为n2， 叶子节点数为n0，则n0＝n2＋1（叶子节点比分支节点多一个） 结点角度： ① 边的角度： 由②—①得： 16 二叉数的存储结构——顺序存储