我们把满足以下两个条件的树型结构叫做二叉树（Binary Tree）：
每个结点的度都不大于2；每个结点的孩子结点次序不能任意颠倒。五种基本形态：
满二叉树： 在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子的结点，并且叶子结点都集中在二叉树的最下一层，则这样的二叉树称为满二叉树。
完全二叉树： 如果对一棵深度为k、有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同，那么这棵二叉树就是一棵完全二叉树 其中，满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
性质1： 在二叉树的第 i i i 层上至多有 2 i − 1 2^{i-1} 2i−1 个结点
性质2： 对任意一棵二叉树 T T T，若终端结点数为 n 0 n _0 n0，而其度数为2的结点数为 n 2 n_2 n2，则 n 0 = n 2 + 1 n_0= n_2+1 n0=n2+1
性质3： 给定 n n n个结点，能构成 C 2 n n / ( n + 1 ) C^n_{2n}/(n+1) C2nn/(n+1) 种二叉树
性质4： 深度为k的二叉树至多有 2 k − 1 2^k-1 2k−1个结点。换句话说，满二叉树中前 k k k层的结点个数为 2 k − 1 2^k-1 2k−1
性质5： 结点总数 N = 度+1
性质1： 叶子结点只可能在层次最大的两层上出现
性质2： 如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子
性质3： 若n为奇数，则每个分支结点都有左子女和右子女；若n为偶数，则编号最大的分支结点（编号为 n / 2 n/2 n/2）只有左子女，没有右子女；
性质4： 具有 n n n个结点的完全二叉树的深度为 └ ㏒ 2 n ┘ + 1 └㏒_2n┘+1 └㏒2n┘+1
性质5： 结点 i i i所在层次（深度）为 └ ㏒ 2 i ┘ + 1 └㏒_2i┘+1 └㏒2i┘+1
性质6： 对于具有 n n n个结点的完全二叉树
若 i = 1 i = 1 i=1, 则 i i i 无双亲结点 若 i > 1 i >1 i>1, 则 i i i 的双亲结点为 └ i / 2 ┘ └i /2┘ └i/2┘若 2 ∗ i > n 2*i > n 2∗i>n, 则 i i i 无左孩子 若 2 ∗ i ≤ n 2*i≤n 2∗i≤n, 则 i 结点的左孩子结点为 2 ∗ i 2*i 2∗i若 2 ∗ i + 1 > n 2*i+1 > n 2∗i+1>n ,则 i i i 无右孩子 若 2 ∗ i + 1 ≤ n 2*i+1≤n 2∗i+1≤n, 则i的右孩子结点为 2 ∗ i + 1 2* i+1 2∗i+1用一组连续的存储单元来存放二叉树的数据元素
对于一般的二叉树，我们必须按照完全二叉树的形式来存储，就会造成空间的浪费。
对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域
若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的链域。
结点类型的定义如下：
typedef struct BTNode { char data; struct BTNode * lchild; struct BTNode * rchild; }BTNode