作者：解学武

链式存储结构存储二叉树，实际上就是采用链表存储二叉树。

既然是使用链表，首先需要构建链表中节点的结构。考虑到存储对象为二叉树，其各个节点最多包含 3 部分，依次是：左孩子、节点数据和右孩子，因此，链表的每个节点都由这 3 部分组成：


图 1 中，Lchild 代表指向左孩子的指针域；data 为数据域；Rchild 代表指向右孩子的指针域。使用此种结点构建的二叉树称为“二叉链表”。

结点结构用代码表示为：

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

如果后期再使用链表的过程中需要频繁地访问某结点的父结点，可以在构建链表时使用下面这种结点结构：


图 2 中，Lchild 指向左孩子；Rchild 指向右孩子；data 为数据域；parent 指向父结点。使用这种结构的结点创建的树称为“三叉链表”。

结点结构代码表示：

typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
    struct BiTNode *parent;
}BiTNode,*BiTree;

图 3 中二叉链表的C语言实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#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)->rchild=NULL;
    (*T)->lchild->data=2;            
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->data=3;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}

运行结果：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。