(
课件网) 树与二叉树 1 树 本节要点： 2 二叉树 1.1 树的概念 1.2 树的特点 2.1 二叉树的概念 2.2 二叉树的分类 2.3 二叉树的性质 树？ 生活中的树 逻辑上的树 常见的树形结构 1.公司组织架构 2.知识点汇总 3.动物分类 共同特征：一对多的非线性关系 1.1 树的概念 树：一种非线性数据结构， 是有 n（n>=0）个节点构成的有限集合 空树：节点n=0的树 1.2 树的特点 1.2 树的特点 当n>0时，n个节点的树有n-1条边 子树：树中某个节点下面的所有节点所构成的树 边 节点 T1 T2 T3 T4 11个节点，10条边 1.2 树的特点 节点的度: 节点所拥有的子树个数 树的度：最大的节点的度（树的宽度） A的度: _____ B的度: _____ C的度：____ 树的度：___ 3 2 0 4 1.2 树的特点 高度或深度：树中节点的最大层数 树的高度：___ ① ② ③ ④ 4 根节点：（开始节点）没有前驱节点 叶子节点：（终端节点）没有后继节点，度为0 1.2 树的特点 A是根节点 E、F、C、H、I、J、K是叶子节点 分支节点：度不为0的节点 内部节点：除根节点外的分支节点 1.2 树的特点 A、B、D、G是分支节点 B、D、G是内部节点 父节点：对于两个以边直接连接的节点， 上端节点称为下端节点的父节点或双亲节点 1.2 树的特点 A是B、C、D的父节点 1.2 树的特点 B、C、D是A的孩子节点 B、C、D互为兄弟节点 孩子节点：下端节点称为上端节点的孩子节点 兄弟节点: 拥有同一个父节点的同层节点 1.2 树的特点 学习任务一 填一填： 1.该树有___个节点，___条边，该树的度是_____,高度是___ 2.该树的叶子节点是_____,内部节点是_____ 3.度为1的节点数有__个，B的孩子节点是___, Q的兄弟节点是__ 12 11 3 6 E F Z P C H B G R Q D 3 E F G P 小明写了一个100以内的正整数，让小红猜； 小红每猜一次， 小明会告诉她“猜大了”还是“猜小了”， 直到猜出正确的结果。 请问小红采用什么方法， 能用最少的次数猜出正确结果？ 猜数游戏 答：用折半猜数法 效率最高 猜数游戏 50 小 75 25 大 小 12 大 37 小 62 大 88 . . . . . . . . . . . . 二叉树 2.1 二叉树的概念 二叉树是一个具有 n（n>=0）个节点的有限集合。 当 n=0时，二叉树是一棵空树； 当 n>0时，则是由根节点、左子树和右子树组成 由于左、右子树也是二叉树，因此子树也可以是空树 二叉树的典型特征：所有节点的度都小于等于2 二叉树的5种形态： 2.1 二叉树的概念 ① ② ③ ④ ⑤ 左子树 右子树 左子树 右子树 学习任务二 画一画： 有3个节点的二叉树有几种不同的形态？ 学习任务二 画一画： 有3个节点的二叉树共有5种不同的形态 ① ② ③ ④ ⑤ 2.2 二叉树的分类 所有的叶子节点都在最底层， 除了叶子节点外，每个结点的度是 2 满二叉树 以下3个二叉树的共同特点是？ 2.2 二叉树的分类 至多只有最下两层中的节点的度数小于2， 且最后一层的叶子结点都依次从左到右分布 完全二叉树 在满二叉树基础上去掉几个节点： 学习任务三 A. B. C. D. 判一判： 下列4棵树是否为完全二叉树？ √ 完全二叉树：至多只有最下两层中的节点的度数小于2，且最后一层的叶子结点都依次从左到右分布 满二叉树 VS 完全二叉树 1.满二叉树一定是完全二叉树 但完全二叉树不一定是满二叉树 2.满二叉树在最后一层从最后一个节点开始， 从右向左连续去掉任意个节点，即为完全二叉树 2.2 二叉树的分类 学习任务四 选一选：下列哪些是满二叉树，哪些是完全二叉树？ ② ③ ④ ⑤ ① ②是满二叉树 ⑤是完全二叉树 二叉树有哪些性质呢？ 因为满二叉树在同层二叉树中 拥有的节点数最多 我们以满二叉树为例来探究下 2.3 二叉树的性质 2.3 二叉树的性质 第①层：1个 第②层：2个 第③层：4个 第④层：8个 1.满二叉树 ... ...
