简单地理解，满足以下两个条件的树就是二叉树：

1. 本身是有序树；

2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

   
   
   图 1 二叉树示意图.gif

二叉树的性质

二叉树具有以下几个性质：

1. 二叉树中，第 i 层最多有 2i-1 个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n₀，度为 2 的结点数为 n₂，则 n₀=n₂+1。

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n₁），那么总结点 n=n₀+n₁+n₂。

同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n₁ 和 n₂ 表示的，即 B=n₁+2n₂。所以，n 用另外一种方式表示为 n=n₁+2n₂+1。

两种方式得到的 n 值组成一个方程组，就可以得出 n₀=n₂+1。

二叉树还可以继续分类，衍生出满二叉树和完全二叉树。

满二叉树

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

图 2 满二叉树示意图.gif

如图 2 所示就是一棵满二叉树。

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

1. 满二叉树中第 i 层的节点数为 2n-1 个。
2. 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有 n 个节点的满二叉树的深度为 log₂⁽ⁿ⁺¹⁾。

完全二叉树

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

图 3 完全二叉树示意图.gif

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

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

[log₂ⁿ]表示取小于 [log₂ⁿ]的最大整数。例如， [log₂⁴] = 2，而 [log25] 结果也是 2。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：

1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
3. 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

二叉树的顺序存储结构

二叉树的存储结构有两种，分别为顺序存储和链式存储。先介绍二叉树的顺序存储结构。

二叉树的顺序存储，指的是使用顺序表
数组存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

有读者会说，满二叉树也可以使用顺序存储。要知道，满二叉树也是完全二叉树，因为它满足完全二叉树的所有特征。

普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。如图1 所示：

图 1 普通二叉树的转化.png

图 1 中，左侧是普通二叉树，右侧是转化后的完全（满）二叉树。
解决了二叉树的转化问题，接下来学习如何顺序存储完全（满）二叉树。
完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

图 2 完全二叉树示意图.gif

例如，存储图 2 所示的完全二叉树，其存储状态如图 3 所示：

图 3 完全二叉树存储状态示意图.png

同样，存储由普通二叉树转化来的完全二叉树也是如此。例如，图 1 中普通二叉树的数组存储状态如图 4 所示：

图 4 普通二叉树的存储状态.png

由此，我们就实现了完全二叉树的顺序存储。

不仅如此，从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。此性质可用于还原数组中存储的完全二叉树，也就是实现由图 3 到图 2、由图 4 到图 1 的转变。

二叉树的链式存储结构及（C语言）实现

图1 普通二叉树示意图.gif

如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，图 1 对应的链式存储结构如图 2 所示：

图 2 二叉树链式存储结构示意图.gif

由图 2 可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：

• 指向左孩子节点的指针（Lchild）；
• 节点存储的数据（data）；

• 指向右孩子节点的指针（Rchild）；

  
  
  图 3 二叉树节点结构.gif

表示该节点结构的 C 语言代码为：

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

图 2 中的链式存储结构对应的 C 语言代码为：

#include <stdio.h>

typedef struct BiTNode{
    int data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;


void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}

程序输出结果：
4

其实，二叉树的链式存储结构远不止图 2 所示的这一种。例如，在某些实际场景中，可能会做 "查找某节点的父节点" 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如图 4 所示：

图 4 自定义二叉树的链式存储结构.gif

这样的链表结构，通常称为三叉链表。

利用图 4 所示的三叉链表，我们可以很轻松地找到各节点的父节点。因此，在解决实际问题时，用合适的链表结构存储二叉树，可以起到事半功倍的效果。