一、定义

链式存储是表示树结构最直观、最常用的一种方法。它的核心思想是：

用链表中的节点来表示树中的每个元素。每个节点不仅包含数据本身，还包含指向其子节点的指针。

二、基本结构

对于一个普通的树（不一定是二叉树），一个典型的链式存储节点结构如下：

// C语言示例  typedef struct TreeNode {      int data;                   // 节点中存储的数据      struct TreeNode *firstChild; // 指向第一个孩子节点的指针      struct TreeNode *nextSibling; // 指向下一个兄弟节点的指针  } Node;

这种结构通常被称为 “孩子-兄弟表示法” 或 “左孩子右兄弟表示法”。

三、基本原理

假设我们有这样一棵树：

        A        / | \       B  C  D      / \    |     E   F   G

用“孩子-兄弟表示法”的链式存储后，它在内存中的逻辑结构会变成一棵二叉树的样子：

      A       /      B ——— C ——— D     /                 /    E ——— F        G

解释：

• firstChild 指针（纵向）：指向该节点的第一个子节点。

• 节点 A 的 firstChild 指向 B。

• 节点 B 的 firstChild 指向 E。

• 节点 D 的 firstChild 指向 G。

• nextSibling 指针（横向）：指向该节点的下一个兄弟节点。

• 节点 B 的 nextSibling 指向 C。

• 节点 C 的 nextSibling 指向 D。

• 节点 E 的 nextSibling 指向 F

四、对于二叉树的链式存储

二叉树是一种特殊的树，每个节点最多有两个子节点（左孩子和右孩子）。它的链式存储结构更为简单：

// 二叉树的链式存储节点  typedef struct BiTNode {      int data;                // 数据域      struct BiTNode *lchild;  // 指向左子节点的指针      struct BiTNode *rchild;  // 指向右子节点的指针  } BiTNode;

对于二叉树：

      A       / \      B   C     / \   \    D   E   F

其链式存储的逻辑关系非常直观：

• A 的 lchild 指向 B，rchild 指向 C。

• B 的 lchild 指向 D，rchild 指向 E。

• C 的 lchild 为空，rchild 指向 F