二叉树的定义

二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。

二叉树中许多概念与树中的概念相同。

在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结点个数，n1表示单分支结点个数，n2表示双分支结点个数。

度为2的树至少有3个结点，而二叉树的结点数可以为0。

度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

归纳起来，二叉树的5种形态：

二叉树抽象数据类型的描述

满二叉树和完全二叉树

在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。

可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次序进行。

满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h且有2h-1个结点的二叉树称为满二叉树。

满二叉树的特点如下：

叶子结点都在最下一层。

只有度为0和度为2的结点。

含n个结点的满二叉树的高度为log2(n+1)，叶子结点个数为n/2+1，度为2的结点个数为n/2。

若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。

同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二叉树相同，图中每个结点外边的数字为对该结点的编号。

完全二叉树的特点如下：

叶子结点只可能出现在最下面两层中。

对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。

如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子；

按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。

二叉树性质

性质1 非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。

证明：

总结点数n=n0+n1+n2。

一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。

总的度数=总分支数=n-1。

则n1+2n2=n0+n1+n2-1，求出n0=n2+1。

性质2 非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。

由树的性质2可推出。

性质3 高度为h的二叉树至多有2h-1个结点（h≥1）。

由树的性质3可推出。

性质4 完全二叉树（结点个数为n）层序编号后的性质。

（1）若完全二叉树的根结点编号为1，对于编号为i（1≤i≤n）的结点有：

若i≤n/2，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点，也就是说，最后一个分支结点的编号为n/2。

若n为奇数，则n1=0，每个分支结点都是双分支结点；若n为偶数，则n1=1，只有一个单分支结点。

若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为2i+1。

若编号为i的结点有左兄弟结点，左兄弟结点的编号为i-1，若有右兄弟结点，右兄弟结点的编号为i+1。

若编号为i的结点有双亲结点，其双亲结点的编号为i/2。

（2）若完全二叉树的根结点编号为0，对于编号为i（0≤i≤n-1）的结点有：

若i≤n/2-1，则编号为i的结点为分支结点，否则为叶子结点，也就是说，最后一个分支结点的编号为n/2-1。

若n为奇数，则n1=0，每个分支结点都是双分支结点；若n为偶数，则n1=1，只有一个单分支结点。

若编号为i的结点有左孩子结点，则左孩子结点的编号为2i+1；若编号为i的结点有右孩子结点，则右孩子结点的编号为2i+2。

若编号为i的结点有左兄弟结点，左兄弟结点的编号为i-1，若有右兄弟结点，右兄弟结点的编号为i+1。

若编号为i的结点有双亲结点，其双亲结点的编号为(i-1)/2。

性质5 具有n个（n＞0）结点的完全二叉树的高度为log2(n+1)或log2n+1。

由完全二叉树的定义和树的性质3可推出。

一棵含有882个结点的二叉树中有365个叶子结点，求度为1的结点个数和度为2的结点个数。

解：这里n=882，n0=365。

由二叉树的性质1可知n2=n0-1=364。

n=n0+n1+n2，即n1=n-n0-n2=882-365-364=153。

所以该二叉树中度为1的结点和度为2的结点个数分别是153和364。

一棵完全二叉树中有501个叶子结点，则至少有多少个结点。

解：该二叉树中有，n0=501。

由二叉树性质1可知n0=n2+1，所以n2=n0-1=500。

n=n0+n1+n2=1001+n1，由于完全二叉树中n1=0或n1=1，则n1=0时结点个数最少，此时n=1001，即至少有1001个结点。

二叉树的顺序存储结构

顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树中的结点。

由二叉树的性质4可知，对于完全二叉树（或满二叉树），树中结点层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。

一棵完全二叉树的顺序存储结构

或者

一般的二叉树 的顺序存储结构

或者

二叉树顺序存储结构采用字符串（假设每个结点值为单个字符）或者列表（数组）存放。

当二叉树中某结点为空结点或无效结点（不存在该编号的结点）时，对应位置的值用特殊值（如'#'）表示。

完全二叉树或满二叉树采用顺序存储结构比较合适

如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。

二叉树的链式存储结构

二叉树的列表存储结构

每个结点为"[结点值，左子树列表，右子树列表]"的三元组，当左或者右子树为空时取值None。类型如下：

二叉树的递归算法设计

对于二叉树b，设f(b)是求解的"大问题"。

f(b->lchild)和f(b->rchild)为"小问题"。

假设f(b->lchild)和f(b->rchild)是可求的，在此基础上得出f(b)和f(b->lchild)、f(b->rchild)之间的关系，从而得到递归体。

再考虑b=NULL或只有一个结点的特殊情况，从而得到递归出口。

二叉树的基本运算及其实现

为了简单，本节讨论的二叉树中所有结点值为单个字符。逻辑结构采用括号表示串，存储结构采用二叉链。

二叉树类设计

二叉树的基本运算算法实现

（1）设置二叉树的根结点SetRoot(b)

（2）求二叉链的括号表示串DispBTree()

（3）查找值为x的结点FindNode(x)

设f(t，x)在以t为根结点的二叉树中查找值为x的结点，找到后返回其地址，否则返回None。

（4）求高度Height()

设以t为根结点二叉树的高度为f(t)，空树高度为0，非空树高度为左、右子树中较大的高度加1。