62二叉树( Binary Tree) 二叉树的定义 一棵二叉树是结点的一个有限集合,该 集合或者为空,或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 特点:1)每个结点的度<2:2)是有序树 (a)(b) R (c)(d) (e) 二叉树的五种不同形庵
6.2 二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该 集合或者为空，或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 特点：1）每个结点的度≤2；2）是有序树
二叉树的抽教据类型 基本操作:p121~p123 二叉树的建立和遍历
基本操作：p121~p123 二叉树的建立和遍历 二叉树的抽象数据类型
二叉树的性质 性质1若二叉树的层次从1开始,则在二叉树的 第i层最多有2个结点。(i≥1) i证明用数学归纳法 性质2深度为k的二叉树最多有2k-1个结点。 (k≥1) 证明用求等比级数前k项和的公式 性质3对任何一棵二叉树,如果其叶结点个数为 np度为2的非叶结点个数为m2,则有 noEn+1
性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2 i-1个结点。(i 1) [证明用数学归纳法] 性质2 深度为k的二叉树最多有 2 k -1个结点。 (k 1) [证明用求等比级数前k项和的公式] 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为n2 , 则有 n0＝n2＋1 二叉树的性质
证明:考设度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定义, n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n1=n0+n1+m2-1 2 0 0-2 +1 同理 三次树:n0=1+n2+2n3 四次树:n0=1+n2+2n3+3n4 K次树:n0=1+n2+2n3+…+(kx-1)nk
证明：若设度为1的结点有n1个，总结点个 数为n，总边数为e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 同理： 三次树： n0=1+n2+2n3 四次树： n0=1+n2+2n3+3n4 … K次树： n0=1+n2+2n3+…+(k-1)nk
定义1满二叉树( Full Binary tree) 定义2完全二叉树( Complete binary tree 若设二叉树的深度为h,则共有h层。除第层 外,其它各层(0~h-1)的结点数都达到最大个数 第h层从右向左连续缺若干结点,这就是完全二 叉树。 ((8 (a)满二叉树 b)完全二叉树
定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的深度为h，则共有h层。除第h层 外，其它各层(0h-1)的结点数都达到最大个数， 第h层从右向左连续缺若干结点，这就是完全二 叉树