二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。

• 左子树和右子树是有顺序的，次序不能任意颠倒。就像人有双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受。

• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。下图中，树1和树2是同一棵树，但它们却是不同的二叉树。就好像你一不小心，摔伤了手，伤的是左手还是右手，对你的生活影响度是完全不同的。

image-20200504202504967

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

1. 空二叉树。
2. 只有一个根结点。
3. 根结点只有左子树。
4. 根结点只有右子树。
5. 根结点既有左子树又有右子树。

特殊二叉树

斜树

顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。

满二叉树

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

下图就是一棵满二叉树，从样子上看就感觉它很完美。

image-20200504203803800

单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。因此，满二叉树的特点有：

（1）叶子只能出现在最下一层。出现在其他层就不可能达成平衡。

（2）非叶子结点的度一定是2。否则就是“缺胳膊少腿”了。

（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如下图所示。

image-20200504205911056

首先从字面上要区分，“完全”和“满”的差异，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的。这里有个关键词是按层序编号。

二叉树的性质

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

性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

性质4：具有n个结点的完全二叉树的深度为|log2n+1|（|x|表示不大于x的最大整数）。

性质5：如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：

1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
2. 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

二叉树的存储

二叉树顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

一棵完全二叉树如下图所示。

image-20200505105041983

将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如下图所示。

image-20200505105156125

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为“∧”而已。

将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如下图所示。

image-20200505110541565

考虑一种极端的情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2k-1个存储单元空间，这显然是对存储空间的浪费，例如下图所示。所以，顺序存储结构一般只用于完全二叉树。

image-20200505130842998

二叉链表

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

lchild	data	rchild

其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

以下是我们的二叉链表的结点结构定义代码。

/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef struct BiTNode                  
{
    /* 结点数据 */
    TElemType data;                     
    /* 左右孩子指针 */
    struct BiTNode *lchild, *rchild;    
} BiTNode, *BiTree;

结构示意图如图

image-20200505132347682