所属分类：php教程
二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链表来指示元素之间的逻辑关系。二叉树的链式存储结构通常有两种存储形式：二叉链表和三叉链表。
php入门到就业线上直播课：进入学习
API 文档、设计、调试、自动化测试一体化协作工具：点击使用
本教程操作环境：windows7系统、c99版本、Dell G3电脑。
二叉树的链式存储结构就是用链表来表示一棵二叉树，即用链表来指示元素之间的逻辑关系。通常有两种存储形式：
链表中每个结点由三个域组成，除了数据域之外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的存储地址。
链表中每个结点由四个域组成，除了数据域之外，还有三个指针域，分别用来给出该结点的左孩子、右孩子和双亲结点所在的存储地址。
二叉树的链式存储结构（C语言详解）
图 1 普通二叉树示意图
如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，图 1 对应的链式存储结构如图 2 所示：
图 2 二叉树链式存储结构示意图
由图 2 可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：
指向左孩子节点的指针（Lchild）；
节点存储的数据（data）；
指向右孩子节点的指针（Rchild）；
图 3 二叉树节点结构
表示该节点结构的 C 语言代码为：
微博登录
QQ登录typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
struct BiTNode *parent;
}BiTNode,*BiTree;登录后复制图 2 中的链式存储结构对应的 C 语言代码为：
#include
#include
#define TElemType int
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->data=3;
(*T)->rchild->lchild=NULL;
(*T)->rchild->rchild=NULL;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->lchild->data=4;
(*T)->lchild->rchild=NULL;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf("%d",Tree->lchild->lchild->data);
return 0;
}
登录后复制程序输出结果：
4
登录后复制其实，二叉树的链式存储结构远不止图 2 所示的这一种。例如，在某些实际场景中，可能会做 "查找某节点的父节点" 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如图 4 所示：
图 4 自定义二叉树的链式存储结构
这样的链表结构，通常称为三叉链表。
利用图 4 所示的三叉链表，我们可以很轻松地找到各节点的父节点。因此，在解决实际问题时，用合适的链表结构存储二叉树，可以起到事半功倍的效果。
相关推荐：《C语言视频教程》
以上就是二叉树的链式存储结构是什么的详细内容，更多请关注zzsucai.com其它相关文章！
