1.二叉树的定义

 

二叉树T：一个又穷的结点集合。

这个结点集合可以为空，若不为空则则它是由根节点及称为其左子树TL和右子树TR的两个不相交的二叉树组成。那么也就是说二叉树具有五种基本形态，如下图所示。

 

图    二叉树的五种基本形态

 二叉树与一般的度为2的树是有区别的：二叉树的子树有左右之分。

 

2.几种特殊的二叉树

 

①斜二叉树(skewed  binary tree)

相当于链表，已经是一个线性结构了。

②完美二叉树(perfect binary tree)或满二叉树(full binary tree)

除了叶结点外的所有结点都有两个子结点，且叶结点比较齐都在同一层

③完全二叉树(complete binary tree)

对于有n个结点的二叉树，如果按照从上至下、从左至右一一进行编号，那么编号为i(i=1~n)的结点所处二叉树的位置与编号为i的结点在满二叉树中的位置一样。

也就是说，完全二叉树就是允许满二叉树中的叶子节点缺失一部分（但只能是一整块右边的，左边还是齐全的）。

                                                                 

 图    斜二叉树　　　　                                             图    满二叉树　　　　　　　　　　　　　　　　                                          图    图完全二叉树

 

3.二叉树的重要性质

 

①二叉树的第i层最多有  2^i-1  个结点（i≥1）

②一个深度为k的二叉树最多有  2^k-1个结点（k≥1）

③对于任意的非空二叉树，若叶子结点有n0个，度为2的结点有n2个，那么有：n0 = n2 + 1

证明：（备忘：结点的度指结点有的子树个数）

设度为1的结点个数为n1，则全部结点的个数可以表示为n0+n1+n2，边一共有0 * n0 + 1 * n1 + 2 * n2条，而对于一个二叉树来说如果有m个点那么就会有m-1条边，那么就有等式n0 + n1 + n2 - 1 = 0 * n0 + 1 * n1 + 2 * n2，化简就能得证。

 

4.二叉树的抽象类型定义

 

①类型名称：二叉树

②数据对象集：一个有穷的结点集合。若不为空，则由根结点和左右两二叉子树构成

③操作集：

isEmpty判断是否为空

traversal遍历二叉树

createBinTree创建二叉树