二叉树基本概念——二叉树（概念、性质、顺序存储，链式存储）、满二叉树与完全二叉树、二叉链表，三叉链表，双亲链表

一、二叉树定义

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

下面是含三个结点的二叉树（方便理解）

---

二、二叉树性质

1、在二叉树的第i层上至多有2^(i-1)个结点（i>=1）：比如第1层只有一个结点（根）

2、深度为k的二叉树至多有2^(k)-1个结点（k>=1）

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

4、具有n个结点的完全二叉树的深度为x+1，（x不大于log2n）（2是底数）

---

三、满二叉树与完全二叉树

满二叉树

一棵深度为k且有2^(k)-1个结点的二叉树称为满二叉树（不存在度为1的结点，只有0和2）

完全二叉树

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应（左右子树也不能颠倒）

下面是我觉得比较好理解满二叉树与完全二叉树的几幅图

---

四、二叉树顺序存储结构（对象：完全二叉树）

用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树的结点元素，即将完全二叉树编号为i的结点元素存储在如下定义的一维数组中下标为i-1的分量中。（下标从0开始）

#define MAX_TREE_SIZE 100//定义二叉树最大结点数
typedef TElemType SqBiTree[Max_Tree_Size];//0号单元存储根结点
SqBiTree bt;

---

五、二叉树链式存储结构（二叉链表）

链式存储包含三个域：（数据域，左指针域，右指针域），二叉链表方便找左右孩子，不方便找双亲（因为没有指向双亲的指针域）

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

---

六、三叉链表

比二叉链表多了一个指向双亲的指针域

typedef struct BiTPNode
 {
   TElemType data;
   struct BiTPNode *parent,*lchild,*rchild; /* 双亲、左右孩子指针 */
 }BiTPNode,*BiPTree;

---

七、双亲链表（数组存储法）

typedef struct BPTNode{//结点结构
    TElemType data;
    int *parent;//指向双亲的指针
    char LRTag;//左，右孩子的标志域
}BPTNode;
typedef struct BPTree{//树结构
    BPTNode *nodes;
    int num_node;//结点数目
    int root;//根结点的位置
}BPTree;

双亲理解图