62二又树( Binary Tree 叉树是树的基础,一般的树可以转化为二叉树来处理。 62.1二叉树的定义 棵二叉树是一有限结点的集合,该集合或者为空(空二叉 树),或者是由一个根结点及其下的两棵互不相交的子二叉树构 成,其中左边的称为左子树,右边的称为右子树。 二叉树是一棵度数<=2的有序树。 6,2.2二叉树的性质 )二叉树的第i层的结点数<=2 (2)高度为k的二叉树的最大结点数=2k+1 (k>=-1) 满二叉树( Full Binary Tree):叶结点在同一层,非叶结点的度数均 为2的二叉树(参见图6.3a) 完全二叉树( Complete Binary Tree):按从上到下、从左到右顺序 编号一棵满二叉树,并按从大到小的顺序连续删除 该满二叉树的若干个结点后剩下的二叉树称为一棵 完全二叉树(参见图6.3b) 20212222021/2/22 4 6.2 二叉树( Binary Tree ) 二叉树是树的基础，一般的树可以转化为二叉树来处理。 6.2.1 二叉树的定义 一棵二叉树是一有限结点的集合，该集合或者为空（空二叉 树），或者是由一个根结点及其下的两棵互不相交的子二叉树构 成，其中左边的称为左子树，右边的称为右子树。 二叉树是一棵度数<= 2 的有序树。 6.2.2 二叉树的性质 （1）二叉树的第i 层的结点数<= （2）高度为k 的二叉树的最大结点数＝ ( k >= -1) 满二叉树( Full Binary Tree )：叶结点在同一层，非叶结点的度数均 为 2 的二叉树（参见图6.3a ） 完全二叉树( Complete Binary Tree )： 按从上到下、从左到右顺序 编号一棵满二叉树，并按从大到小的顺序连续删除 该满二叉树的若干个结点后剩下的二叉树称为一棵 完全二叉树（参见图6.3b ） 2 i 2 k+1 - 1