树与二叉树 A B C D E G H F I 树 树是一种重要的非线性数据结构，直观的看，它是数据元素（在树中称之为节点）按分支关系组织起来的结构，与自然界的树很像。 树 日常生活中很多事物可以用树形图来表示，如家族族谱、动物分类等，如图所示 树 日常生活中很多事物可以用树形图来表示，如家族族谱、动物分类等，如图所示 树的基本概念 定义：是n（n>=0）个节点的有限集合 若n=0,称为空树； 若n>0，则它满足如下两个条件； 1）有且仅有一个特定的称为根的节点； 2）其余节点可分为m（m>=0）个互不相交的有限集合T1,T2,T3.....Tm，其中每一个集合本身又是一棵树，并称为根的子树。 节点A有三棵子树 节点B有两棵子树 树的基本术语 A节点是B节点的双亲节点 B节点是A节点的孩子 叶子节点 B、C、D是兄弟节点 1、节点 (1)节点：集合中的元素 (2)孩子节点(子节点)：节点的子树的根称为该节点的孩子节点； (3)双亲节点(父节点) ：B节点是A节点的孩子，则A节点是B节点的双亲节点； (4)兄弟节点：同一双亲的孩子节点； 树的基本术语 根节点 分支节点 叶子节点 1、节点 (1)根节点：没有父亲(双亲)的节点。在树中有且仅有一个根节点。 (2)分支节点：除根节点外，有孩子的节点称为分支节点。 (3)叶节点：没有孩子的节点称为树叶。 根节点到每一个分支节点或叶节点的路径是唯一的路径。 根节点的度为3 B节点的度为2 叶子节点度为0 树的基本术语 3、树基本属性 (1)节点层：根节点的层定义为1；根的孩子为第二层节点，依此类推 (2)树的深度：树中最大的节点层 (3)节点的度：节点子树的个数 (4)树的度： 树中最大的节点度 第1层 第2层 第3层 第4层 树的深度 树的特点 非空树(n>0)的特点： (1)有且仅有一个根节点 (2)除了根节点外，任何一个节点都有且仅有一个前驱 (3)每个节点可以有0个或多个后继。 根节点 分支节点 叶子节点 练一练 一 (1)该树共有 节点。 (2)根节点的名称是 ，它有 个孩子节点。 (3)节点B、C、D的度分别是 ，该树的度 。 (4)该树 个分支节点， 个叶子节点。 (5)节点H的层数 ，树的深度 。 (6)节点B的父节点 、兄弟节点 、孩子节点 。 13 3 2 1 3 3 5 7 3 4 A C、D E、F A 二叉树 二叉树是n（n≥0）个节点的有限集合： ① n = 0时，二叉树是一棵空树。。 ② 当n ≠ 0时，二叉树是由一个根节点(N)和两个互不相交的集合被称为根的左子树(L)和右子树(R)组成。左子树和右子树又分别是一棵二叉树。 二叉树的基本概念 节点A的右子树 ①每个节点至多只有两棵子树。 ②左右子树不能颠倒 二叉树的特点 节点A的右子树 二叉树的五种基本形态 (a) 空二叉树 A A B (c) 根和左子树 A (b) 根和空二叉树 A C (d) 根和右子树 A C B (e) 根和左右子树 ①二叉树第i层至多有2i?1个节点（i≥1） ? 二叉树的性质 应用： （1）如图所示， 第1层上最多只有 个节点； 第2层上最多只有 个节点，以此类推， 第i层上最多只有 个节点。 1 2 2i?1 ? ②深度为k的二叉树多有2k?1个节点（i≥1） ? 二叉树的性质 应用： 根据性质①可知，第1层节点数最多为20。第2层节点数最多为21，以此类推，深度为k的二叉树节点最多有20+21+22+……+2k=2k-1 （2）某二叉树深度为4，则该二叉树最多有 个节点。 15 ③在任意一棵二叉树中，若度为2的节点数量为n2 ，叶子节点数为n0，则n0＝n2＋1（叶子节点比分支节点多一个） 二叉树的性质 应用： 如图甲，度为2的节点数为5，叶子节点数为6； 如图乙：度为2的节点数为 ，叶子节点数为 。 图甲 图乙 5 6 特点：①每个节点的度为2（具有两个非空子树），或者度数为0（叶子节点） ②所有叶子节点都在同一层 特殊都二叉树———满二叉树 应用： 根据二叉树性质可知： （1）满二叉树第k层上的节点数一定为 。 （2）一个深度为k的满二叉树 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
