二叉树的顺序存储的缺点
因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或少会存在空间浪费的现象
图 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;// 结点 2T->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->data = 2;T->lchild->rchild = NULL;// 结点 3T->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;// 结点 2T->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->data = 2;T->lchild->rchild = NULL;T->lchild->parent = T;// 结点 3T->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); // 2return 0;}
