数据结构之二叉树的存储方式

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1.顺序存储

1. 顺序存储
   顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树，
2. 因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。
3. 二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

完全二叉树的顺序存储

经典结论：

假设parent是父亲结点在数组中的下标

则左孩子 = parent*2+1

右孩子 = parent* 2 + 2

假设孩子的下标是child，不管左孩子还是右孩子 parent = (child - 1) / 2

如果算出来下标不再数组范围内->说明其没有孩子/没有父亲结点->根节点

非完全二叉树的顺序存储

不是完全二叉树也可也用数组存储，但是可能会浪费很多空间

2.链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式结构又分为二叉链和三叉链

二叉链

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

三叉链

// 三叉链
typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；