作者：解学武

上一节介绍了二叉树的顺序存储结构，通过学习你会发现，其实二叉树并不适合用顺序表存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或多会存在内存浪费的情况。

本节我们学习二叉树的链式存储结构。

所谓二叉树的链式存储，其实就是用链表存储二叉树，具体的存储方案是：从树的根节点开始，将各个节点及其左右孩子使用链表存储。例如图 1 是一棵普通的二叉树，如果选择用链表存储，各个结点的存储状态如下图所示：


由图 2 可知，采用链式存储二叉树时，树中的结点由 3 部分构成（如图 3 所示）：

• 指向左孩子节点的指针（Lchild）；
• 节点存储的数据（data）；
• 指向右孩子节点的指针（Rchild）；

表示节点结构的 C 语言代码为：

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

用链表存储图 2 所示的二叉树，对应的 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)->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;
}

//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("根节点的左孩子结点为：%d\n", Tree->lchild->data);
    printf("根节点的右孩子结点为：%d\n", Tree->rchild->data);
    DestroyBiTree(Tree);
    return 0;
}

程序输出结果：

根节点的左孩子结点为：2
根节点的右孩子结点为：3

实际上，二叉树的链式存储结构远不止图 2 所示的这一种。某些实际场景中，可能会在树中做类似 "查找某节点的父节点" 的操作，可以在节点结构中再添加一个指针域，用于各个节点指向它的父亲节点，如图 4 所示：

这样的链表结构，通常称为三叉链表。

利用图 4 所示的三叉链表，可以很轻松地找到各节点的父节点。因此，在解决实际问题时，构建合适的链表结构存储二叉树，可以起到事半功倍的效果。