数据结构--树4.2（二叉树）

目录

一、二叉树的定义和特点

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.