文章目录序言正文总结
上一节对二叉树的顺序记忆进行了说明，通过学习可以看出，其实二叉树不适合使用数组记忆。 因为并不是所有的二叉树都是完整的二叉树，所以在普通的二叉树中，使用顺序表记忆的话往往会浪费空间。 本节学习二叉树的连锁记忆结构。
正文
图1常见二叉树示意图
如图1所示，这是普通的二叉树，将其作为链存储，从树的根节点开始，将各个节点及其左右的孩子作为链接列表存储即可。 因此，与图1对应的链存储器结构如图2所示。
图2二叉树的链式存储结构示意图
从图2可以看出，连锁性地收纳二叉树时，其节点结构由3个部分构成()
指向左侧子节点的指针(Lchild；
存储在节点上的数据(data；
指向右侧子节点的指针(Rchild )；
图3二叉树的节点结构
表示此节点结构的c语言代码如下：
# definetelemtypeinttypedefstructbitnode { telemtypedata； //数据域struct BiTNode *lchild； //左儿童指针struct BiTNode *rchild； //右儿童指针(}BiTNode，*BiTree； 与图2中的链存储结构对应的c语言代码如下：
# include stdio.h # include stdlib.h # definetelemtypeinttypedefstructbitnode { telemtypedata； //数据域struct BiTNode *lchild； //左儿童指针struct BiTNode *rchild； //右儿童指针(}BiTNode，*BiTree； voidcreatebitree(bitree*t ) (t=) bitnode* ) malloc ) sizeof ) bitnode )； (t ) -数据=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 )； 返回0； }程序输出结果：
4
实际上，二叉树的连锁存储结构不仅如图2所示。 例如，在实际场景中，可能需要执行“查找节点的父节点”操作，如图4所示。 在这种情况下，可以在节点结构中添加指针字段，以便每个节点都指向父节点。
图4定制二叉树的连锁记忆结构
这种链表结构通常称为三叉链表。
此时，结构中存储父节点的指针增加了一个。
# definetelemtypeinttypedefstructbitnode { telemtypedata； //数据域struct BiTNode *lchild； //左儿童指针struct BiTNode *rchild； //右儿童指针struct BiTree *parent； //指向父母节点的指针}BiTNode，*BiTree； 利用图4所示的三叉链表，可以很容易地发现各节点的父节点。 因此，在解决实际问题时，用合适的链表结构存储二叉树可以取得更多的成果。
本文简要总结了二叉树的连锁存储结构，有错误的地方敬请指正。