二叉树的定义及其主要特性

二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是 #card=math&code=n%5C%20%28n%5Cge%200%29&id=hGorJ) 个结点的有限集合：

1. 或者为空二叉树，即 。
2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一颗子树，也要区分它是左子树还是右子树。

二叉树与度为 2 的有序树的区别：

1. 度为 2 的树至少有 3 个结点，而二叉树可以为空。
2. 度为 2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为 2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。

   几个特殊的二叉树

满二叉树。一棵高度为 ，且含有 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 2 （不存在度为 1 的结点）。可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 1 ）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 的结点，若有双亲，则其双亲为 ，若有左孩子，则左孩子为 ；若有右孩子，则右孩子为 。

完全二叉树。高度为 、有 个结点的二叉树，当且仅当其每个结点都与高度为 的满二叉树中编号为 的结点一一对应时，称为完全二叉树。就是对应相同高度的满二叉树缺失最下层最右边的一些连续叶子结点。其特点如下：

1. 若 ，则结点 为分支结点，否则为叶子结点。
2. 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
3. 若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。
4. 按层序编号后，一旦出现某结点（编号为 ）为叶子结点或只有左孩子，则编号大于 的结点均为叶子结点。
5. 若 为奇数，则每个分支结点都有左孩子和右孩子；若 为偶数，则编号最大的分支结点（编号为 ）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

• 左子树上所有结点的关键字均小于根结点的关键字；
• 右子树上的所有结点的关键字均大于根结点的关键字；
• 左子树和右子树又各是一棵二叉排序树。

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过 1 。

二叉树的性质

（1）非空二叉树上的叶子结点数等于度为 2 的结点数加 1，即 。

证明：设度为 0，1 和 2 的结点个数分别为 ， 和 ，结点总数 。再看二叉树中的分支树，除根结点外，其余结点都有一个分支进入，设 为分支总数，则 。由于这些分支是由度为 1 或 2 的结点射出的，所以又有 。于是得 ，则 。

拓展到任意一棵树，若结点数量为 ，则边的数量为 。

（2）非空二叉树上第 层上至多有 个结点 （ ），可扩至 m 叉树

（3）高度为 的二叉树至多有 个结点（ ）。高度为 的 叉树至多有 个结点，推出。

（4）具有 个（）结点的完全二叉树的高度 为 或

证明：高度为 的满二叉树共有 个结点，高度为 的满二叉树共有 个结点，可得：

高度为 的满二叉树共有 个结点，高为 的完全二叉树至少有 个结点，至多有 个结点，可得：

（5）对于完全二叉树，可以由的结点数 推出度为 0、1 和 2 的结点个数为 、和 。

• 完全二叉树最多只有一个度为 1 1 的结点，即： ；
• ，两边各加上 可得： 可推出 一定为奇数；

根据上两个推论得：

• 若完全二叉树有 （偶数）个结点，则必有
• 若完全二叉树有 （奇数）个结点，则必有

  二叉树的存储结构

  顺序存储结构

  二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 的结点元素存储在一维数组下标为 的分量中。（这种存储结构建议从数组下标 1 开始存储树中的结点） ```c

  define MaxSize 100

  struct TreeNode { int value; bool isEmpty; };

void InitTree() { TreeNode t[MaxSize]; for (int i = 0; i < MaxSize; i++) { t[i].isEmpty = true; } }

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为 ![](https://g.yuque.com/gr/latex?h#card=math&code=h&id=kbc0Q) 且只有 ![](https://g.yuque.com/gr/latex?h#card=math&code=h&id=ZH2me) 个结点的单支树却需要占据近 ![](https://g.yuque.com/gr/latex?2%5Eh-1#card=math&code=2%5Eh-1&id=mEgki) 个存储单元。
<a name="57b79a12"></a>
### 链式存储结构
由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含 3 个域：数据域 `data`、左指针域 `lchild` 和右指针域 `rchild`。![](https://g.yuque.com/gr/latex?n#card=math&code=n&id=Ta1mk) 个节点的二叉链表共有 ![](https://g.yuque.com/gr/latex?n%2B1#card=math&code=n%2B1&id=fyYSt) 个空链域。
```c
typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
    // struct BiTNode *parent;  // 根据实际需求决定是否加父指针
} BiTNode, *BiTree;
int main() {
    // 定义一棵空树
    BiTree root = nullptr;
    // 插入根节点
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = {1};
    root->lchild = nullptr;
    root->rchild = nullptr;
    // 插入新结点
    BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
    p->data = {2};
    p->lchild = nullptr;
    p->rchild = nullptr;
    root->lchild = p;
}

找到指定结点的左右孩子结点十分容易，但如果要寻找父节点只能从根结点开始遍历寻找。可以在结构体中额外定义父节点指针（三叉链表）。