二叉树的定义

二叉树（Binary Tree）是个结点所构成的集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如图1二叉树示例图：

二叉树与树都具有递归性质，二叉树与树的区别主要有：

• 二叉树每个结点至多只有两棵子树，也就是说不存在度大于2的结点。
• 二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树具有的五种基本形态：

• 空二叉树。
• 只有一个根结点。
• 根结点只有左子树。
• 根结点只有右子树。
• 根结点既有左子树又有右子树。

满二叉树

如果二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树。

满二叉树除了满足普通二叉树的性质，还具有以下性质：

• 满二叉树中第层的结点数为个。
• 深度为的满二叉树必有个结点，叶子数为。
• 满二叉树中不存在度为1的结点，每一个分支点中都两棵深度相同的子树，且叶子结点都在最底层。
• 具有个结点的满二叉树的深度为。

完全二叉树

如果二叉树中除去最后一层结点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

如图4a) 所示是一棵完全二叉树，图4b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为。

表示取小于的最大整数。例如，而 结果也是2。

二叉树的性质

• 在二叉树的第层上至多有个结点（）。
• 深度为的二叉树至多有个结点（）。
• 对任何一棵二叉树，如果其终端结点数为，度为2的结点数为，则。
• 具有个结点的完全二叉树的深度为 （[x]表示不大于x的最大整数）。
• 如果对一棵有个结点的完全二叉树（其深度为）的结点，按层序编号（从第1层到第层，每层从左到右），对任一结点有：

a. 如果，则结点是二叉树的根，无双亲；如果，则其双亲是结点。

b. 如果，则结点无左孩子（为叶子结点）；否则其左孩子是结点。

c. 如果，则结点无右孩子；否则其右孩子是结点。