6.2.1　二叉树的概念

1.二叉树的定义

二叉树（binary tree）是个有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态，如图6－5所示。

图6－5 二叉树的五种基本形态

2.二叉树的相关概念

（1）结点的度。结点所拥有的子树的个数称为该结点的度。

（2）叶结点。度为0的结点称为叶结点，或者称为终端结点。

（3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。

（4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。

（5）路径、路径长度。如果一棵树的一串结点n1，n2，…，nk有如下关系：结点ni是ni＋1的父结点（1≤i＜k），就把n1，n2，…，nk称为一条由n1至nk的路径。这条路径的长度是k－1。

（6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。

（7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。

（8）树的深度。树中所有结点的最大层数称为树的深度。

（9）树的度。树中各结点度的最大值称为该树的度。

（10）满二叉树。

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图6－6所示，图6－6（a）就是一棵满二叉树，图6－6（b）则不是满二叉树，因为虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。

图6－6 满二叉树和非满二叉树示意图

（11）完全二叉树。

一棵深度为k、有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图6－7所示，图6－7（a）为一棵完全二叉树，图6－7（b）和图6－6（b）都不是完全二叉树。

图6－7 完全二叉树和非完全二叉树示意图