25树 25.1树的定义:由一个或多个结点组成的有限集合。仅有 个根结点,结点间有明显的层次结构关系。 A B E G 现实世界中,能用树的结构表示的例子: 学校的行政关系、书的层次结构、人类的家族血缘关 系等。 202l/2/22
2021/2/22 7 2.5 树 2.5.1 树的定义：由一个或多个结点组成的有限集合。仅有 一个根结点，结点间有明显的层次结构关系。 A C G T2 D H I T3 J M B E K L T1 F 现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关 系等
介绍几个概念: 结点(Node):树中的元素,包含数据项及若干指向其 子树的分支。 结点的度( Degree):结点拥(A子树数。 结点的层次:从根结点开始算起,根为第一层。 叶子(Lea)为零的结点称端 孩子(T B 么 兄弟 E G 双亲 双亲 深度(K ① 结点的取层 森林( Forest,):M棵互不相交的枓 2021/2/22
2021/2/22 介绍几个概念： 8 结点（Node）：树中的元素，包含数据项及若干指向其 子树的分支。 结点的度（Degree）：结点拥有的子树数。 结点的层次：从根结点开始算起，根为第一层。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点子树的根称为该结点的孩子结点。 兄弟（Sibling）：同一双亲的孩子。 双亲（Parent）：孩子结点的上层结点，称为这些结点的 双亲。 深度（Depth)： 树中结点的最大层次数。 森林（Forest）：M棵互不相交的树的集合。 A C G T2 D H I T3 J M B E K L T1 F
252二叉树( Binary Tree) 1、二叉树的定义及其性质 (1)二叉树的定义 因为树的每个结点的度不同,存储困难,使对树的处理算法! 很复杂。所以引出二叉树的讨论。 仅有 右子树 空二叉树根结点为空 左子树 左右子树 为空 均非空 二叉树的五种基本形态 202l/2/22
2021/2/22 9 2.5.2 二叉树 （Binary Tree） 1 、二叉树的定义及其性质 (1) 二叉树的定义 二叉树的五种基本形态 二叉树一种特殊的树型结构，特点是树中每个结点只有两棵 子树，且子树有左右之分，次序不能颠倒。 空二叉树 仅有 根结点 右子树 为空 左子树 为空 左右子树 均非空 因为树的每个结点的度不同，存储困难，使对树的处理算法 很复杂。所以引出二叉树的讨论
10 二叉数是n(n≥0)个结点的有限集合。它或为空 数(n=0),或由一个根结点和两棵分别称为根的左子 树和右子树的互不相交的二叉数组成。 特别要注意:二叉数不是树的特殊情况。 a a 两棵不同的二叉数 2/22 202l/2/
2021/2/22 10 二叉数是n(n0)个结点的有限集合。它或为空 数(n=0),或由一个根结点和两棵分别称为根的左子 树和右子树的互不相交的二叉数组成。 特别要注意：二叉数不是树的特殊情况。 a a b b 两棵不同的二叉数
ll (2)二叉树的基本性质 A、二叉树的第谌上至多有2H(i≥1)个结点。 6 14 第三层上(i=3),有23-1=4个节点。 第四层上(i=4),有24-1=8个节点。 2/22 202l/2/
2021/2/22 11 A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 (2) 二叉树的基本性质 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 第三层上(i=3)，有2 3-1=4个节点。 第四层上(i=4)，有2 4-1=8个节点