一.二叉树的概念

1.二叉树的性质

　　二叉树的每个节点最多有两个子节点，分别称为左孩子和右孩子，以他们为根的子树称为左子树和右子树。

　　二叉树的第 i 层最多有 2^(i-1) 个节点。如果每层的节点数都是满的，称他为满二叉树。图例：

　　如果这个二叉树只是在最后一层有缺失，且缺失的编号都在最后，则成为完全二叉树。图例：

　　最上面的节点是二叉树的根，他是唯一没有父节点的节点。从根到节点 u 的路径长度定义为 u 的深度，节点 u 到它的叶子节点的最大路径长度定义为节点 u 的高度。根的高度最大，称为树的高。

二.二叉树的存储结构

　　二叉树一个节点的存储，包括节点的值，左右子节点，有静态和动态两种存储方法。

　  1.动态二叉树

struct Node
{
    int value;//节点的值
    node *lson,*rson;//指向左右节点
};

　　注意：需要管理，小心出错。

　　2.静态二叉树

struct Node
{
    int value;
    int lson,rson;//左右孩子
}tree[N];

　　3.访问

　　一颗节点总数量为 k 的完全二叉树，设 1 号节点为根节点，有以下性质：

　　(1). 编号 i>1 的节点，其父节点编号为 i/2

　　(2). 如果 2i>k，那么节点 i 没有孩子；如果 2i+1>k，那么节点 i 没有右孩子

　　(3). 如果节点 i 有孩子，那么他的左孩子是节点 2i，右孩子是节点 2i+1