目录
一、二叉树的定义和特点
1、定义
2、特点
二、二叉树的基本形态
1、空二叉树
2、只有一个根结点
3、根结点只有左子树
4、根结点只有右子树
5、根结点既有左子树又有右子树
6、斜树
7、满二叉树
8、满二叉树和完全二叉树
三、二叉树的性质
一、二叉树的定义和特点
1、定义
二叉树(Binary Tree)是n(n>0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
2、特点
(1) 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。(不是都需要两棵子树,而是最多可以是两棵,没有子树或者有一棵子树也都是可以的。
(2)左子树和右子树都是有顺序的,次序不能颠倒。
二、二叉树的基本形态
1、空二叉树
2、只有一个根结点
3、根结点只有左子树
4、根结点只有右子树
5、根结点既有左子树又有右子树
1 2 3 4 5
6、斜树
斜树是一定要一斜到底。
7、满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有子叶都在同一层上,这样的二叉树称为满二叉树。
特点:
(1)叶子只能出现在最下一层。
(2)非叶子结点的度一定是2。
(3)在同样深度的二叉树中,满二叉树的结点个数一定最多,同时叶子也是最多。
8、满二叉树和完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点位置完全相同,则这棵二叉树称为完全二叉树。
满二叉树
完全二叉树
特点:
(1)叶子结点只能出现在最下两层。
(2)最下层的叶子一定集中在左部连续位置。
(3)倒数第二层,若有叶子结点,一定都在右部连续 位置
(4)如果结点度为1,则该结点只有左孩子
(5)同样结点树的二叉树,完全二叉树的深度最小。
三、二叉树的性质
1、在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。
2、深度为k的二叉树至多有2^(k-1)个结点(k>=1)。
3、对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1.