二叉树（Binary Tree）是由n（n≥0）个节点的有限集合构成，此集合或者为空集，或者由一个根节点及两棵互不相交的左右子树组成，并且左右子树都是二叉树，如图1-7所示。二叉树可以是空集合，根可以有空的左子树或空的右子树。

 

（1）二叉树的特点

二叉树具有以下两个特点：

1）非空二叉树只有一个根节点。

2）每一个节点最多有两棵子树，且分别称为该节点的左子树和右子树。

在二叉树中，一个节点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个节点既没有左子树也没有右子树时，该节点即为叶子节点。

（2）满二叉树与完全二叉树

1）满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，如图1-8所示。

2）完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点，如图1-9所示。

 

如果有一棵具有n个节点的深度为k的完全二叉树，则它的每一个节点都与深度为k的满二叉树中编号为1~n的节点一一对应。

（3）二叉树的基本性质

性质1：在二叉树的第k层上至多有2k-1个节点（k≥1）。

性质2：深度为m的二叉树至多有2m-1个节点。

性质3：对任何一棵二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个。

性质4：具有n个节点的完全二叉树的深度至少为【log2n】+ 1，其中【log2n】表示log2n的整数部分。

性质5：具有n个节点的完全二叉树深度为【log2n】+ 1或【log2(n+1)】。

性质6：如果对一棵有n个节点的完全二叉树的节点按层序编号（从第1层到第【log2n】+1层，每层从左到右），则对任一节点i（1≤i≤n）有：

1）如果i=1，则节点i无双亲，是二叉树的根；如果i>1，则其双亲是节点【i/2】。

2）如果2i≤n，则节点i为叶子节点，无左孩子；否则，其左孩子是节点2i。

3）如果2i+1≤n，则节点i无右孩子；否则，其右孩子是节点2i+1。

（4）二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储节点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后继节点（两个子节点），因此，用于存储二叉树的存储节点的指针域有两个：一个用于指向该节点的左子节点的存储地址，称为左指针域；另一个用于指向该节点的右子节点的存储地址，称为右指针域。