Algorithms and Datastrucstures:Trees 5.2.1二叉树的定义 图5.2列出二叉树的5种基本形态，图5.2(d)和图5.2（e)是不同的两棵二叉树。 (a) (b) 左子树 右子树 左子树 右子树 根和空的 (c) (d) (e) 空二叉树 左右子树 根和左右子树根和左子树 根和右子树 图5.2二叉树的五种基本形态 11 ALDS
11 物料管理 ALDS 11 Algorithms and DataStrucstures:Trees 5.2.1 二叉树的定义 (a) 空二叉树 (b) 根和空的 左右子树 (c) 根和左右子树 (d) 根和左子树 (e) 根和右子树 图5.2 二叉树的五种基本形态 图5.2列出二叉树的5种基本形态，图5.2(d) 和图5.2（e）是不同的两棵二叉树。 左 子 树 右 子 树 左 子 树 右 子 树
Algorithms and Datastrucstures:Trees 二叉树与树的差别 观察图5.3。这是具有相同结点的二棵二叉树。图5.3()的二叉树，其左子树为结点B ,右子树为空。而图5.3(b)的二叉树，其右子树为结点B,左子树为空。根据二叉树 的定义它们是完全不同的二棵二叉树，因为空也是二叉树。但是，如果把它们做为树 对待，它们是完全相同的。因为，根据树的定义，树至少有一个结点，不可以为空。 仅由结点B构成的子树在()、(b)二种表示方法中，都是根结点的一棵子树，而且只 有这一棵子树。 A B B (a) (b) 图5.3二叉树的实例 12 ALDS
12 物料管理 ALDS 12 Algorithms and DataStrucstures:Trees 二叉树与树的差别 (a) A B A B (b) 图5.3 二叉树的实例 观察图5.3。这是具有相同结点的二棵二叉树。图5.3(a)的二叉树，其左子树为结点B ，右子树为空。而图5.3(b)的二叉树，其右子树为结点B，左子树为空。根据二叉树 的定义它们是完全不同的二棵二叉树，因为空也是二叉树。但是，如果把它们做为树 对待，它们是完全相同的。因为，根据树的定义，树至少有一个结点，不可以为空。 仅由结点B 构成的子树在(a)、(b)二种表示方法中，都是根结点的一棵子树，而且只 有这一棵子树
Algorithms and Datastrucstures:Trees 结点总数为3的所有二叉树的不同形状 13 ALDS
13 物料管理 ALDS 13 Algorithms and DataStrucstures:Trees 结点总数为3 的所有二叉树的不同形状
Algorithms and Datastrucstures:Trees 5.2.2二叉树的性质 性质1：一棵非空二叉树的第层上最多有21个结点(1≥1)。 1层：结点个数21-1=1个 2层：结点个数221=2个 3层：结点个数23-1=4个 证明：当i=1时，只有一个根结点，2-1=20=1，命题成立。 假定对于所有的j,1≤j≤k,命题成立。即第j层上至多有21个结点。 由归纳假设可知，第j=k层上至多有2k1个结点。 若要使得第k+1层上结点数为最多，那么，第k层上的每个结点都必须 有二个儿子结点。 因此，第k+1层上结点数最多为为第k层上最多结点数的二倍，即： 2X2k-1=2k+1-1=2k。 所以，命题成立。 14 ALDS
14 物料管理 ALDS 14 Algorithms and DataStrucstures:Trees 5.2.2 二叉树的性质 •性质1：一棵非空二叉树的第i层上最多有2 i-1个结点（i≥1）。 B C D E F L A 1层：结点个数 21-1=1个 2层：结点个数 22-1=2 个 3层：结点个数 23-1=4 个 证明：当i=1时，只有一个根结点，2 i-1=2 0 =1,命题成立。 假定对于所有的j，1≤j≤k,命题成立。即第j层上至多有2 j-1个结点。 由归纳假设可知，第j = k层上至多有2 k-1个结点。 若要使得第k+1层上结点数为最多，那么，第 k层上的每个结点都必须 有二个儿子结点。 因此，第k+1层上结点数最多为为第k层上最多结点数的二倍，即： 2×2 k-1＝2 k+1-1＝2 k。 所以，命题成立
Algorithms and Datastrucstures:Trees 二叉树的性质 性质2一棵高度为k的二叉树，最多具有2k一1个结点。 证明： 这棵二叉树中的每一层的结点个数必须最多。 根据性质1，第i层的结点数最多为等于21，因此结点个数N最多为： k N=∑2i-1=2k-1 i-1 15 ALDS
15 物料管理 ALDS 15 Algorithms and DataStrucstures:Trees 二叉树的性质 性质2 一棵高度为k的二叉树，最多具有2 k－1个结点。 证明： 这棵二叉树中的每一层的结点个数必须最多。 根据性质1，第i层的结点数最多为等于2 i-1 ，因此结点个数N 最多为： N ＝ 2 i-1 ＝2 k-1 k ∑ i=1