二叉树的顺序存储的缺点
因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或少会存在空间浪费的现象
图 1 普通二叉树的转化
如上图 1，普通二叉树里只有二个元素，最好的存储方式当然是开辟相对应的空间，但是顺序存储结构却让我们不能这么做！也就是说我们此时必须花更多的空间去存储相对少的元素
二叉树的链式存储
先慢慢介绍一下链式存储的节点结构！！！
图 2 普通二叉树示意图
如上图 2 所示，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储
因此，图 2?对应的链式存储结构如下图 3?所示：
图 3 二叉树链式存储结构示意图
?由上图 3?可知，采用链式存储二叉树时，其节点结构由 3 部分构成：
图 4?二叉树节点结构
?此时我们直接用结构体声明一下节点的类型！！！and 头文件
#include <stdio.h>
#include <stdlib.h>
typedef struct MyBiTNode{
int data; // 数据域
struct MyBiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode;然后根据图 3 来定义主要函数体（自行消化）
BiTNode *CreateBiTree(BiTNode *T){
// 结点 1
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = 1;
// 结点 2
T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
T->lchild->data = 2;
T->lchild->rchild = NULL;
// 结点 3
T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
T->rchild->data = 3;
T->rchild->lchild = NULL;
T->rchild->rchild = NULL;
// 结点 4
T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
T->lchild->lchild->data = 4;
T->lchild->lchild->lchild = NULL;
T->lchild->lchild->rchild = NULL;
return T;
}
int main() {
BiTNode *Tree = NULL; // 结构体指针指向空
Tree = CreateBiTree(Tree); // 传入结构体指针
printf("%d\n",Tree->lchild->lchild->data); // 4
return 0;
}但是还不能算真的实现了二叉树的链式存储（还不够完善）
在某些实际场景中，可能需要查找某节点的父节点，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点
优化后的链式存储结构如下图 5?所示（通常称为三叉链表）：
图 5?优化后二叉树的链式存储结构
?此时我们直接用结构体声明一下节点的类型！！！and 头文件
#include <stdio.h>
#include <stdlib.h>
typedef struct MyBiTNode{
int data; // 数据域
struct MyBiTNode *lchild, *rchild; // 左右孩子指针
struct MyBiTNode *parent; // 父指针
} BiTNode;?然后根据图 5?来定义主要函数体（自行消化）
BiTNode *CreateBiTree(BiTNode *T){
// 结点 1
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = 1;
T->parent = NULL;
// 结点 2
T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
T->lchild->data = 2;
T->lchild->rchild = NULL;
T->lchild->parent = T;
// 结点 3
T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
T->rchild->data = 3;
T->rchild->lchild = NULL;
T->rchild->rchild = NULL;
T->rchild->parent = T;
// 结点 4
T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
T->lchild->lchild->data = 4;
T->lchild->lchild->lchild = NULL;
T->lchild->lchild->rchild = NULL;
T->lchild->lchild->parent = T->lchild;
return T;
}
int main() {
BiTNode *Tree = NULL; // 结构体指针指向空
Tree = CreateBiTree(Tree); // 传入结构体指针
printf("%d\n",Tree->lchild->lchild->parent->data); // 2
return 0;
}