一、定义

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

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

二、基本结构

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

// 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

二叉树的存储和遍历

（1）使用递归构建方式

#include <iostream>  #include <vector>  using namespace std;    // 二叉树节点（链式存储）  struct TreeNode {      int data;      TreeNode* left;      TreeNode* right;      TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}  };    // 核心：递归构建二叉树（根据层序遍历数组）  // 参数：nums-层序数组（-1表示空节点），index-当前节点在数组中的索引  TreeNode* buildTreeRecursive(const vector<int>& nums, int index) {      // 递归终止条件：索引越界 或 该位置为空节点（-1）      if (index >= nums.size() || nums[index] == -1) {          return nullptr;      }        // 1. 创建当前节点      TreeNode* node = new TreeNode(nums[index]);        // 2. 递归构建左子树（左子节点索引：2*index + 1）      node->left = buildTreeRecursive(nums, 2 * index + 1);        // 3. 递归构建右子树（右子节点索引：2*index + 2）      node->right = buildTreeRecursive(nums, 2 * index + 2);        return node;  }    // 先序遍历  void preOrder(TreeNode* node) {      if (node == nullptr) return;      cout << node->data << " ";      preOrder(node->left);      preOrder(node->right);  }    // 中序遍历  void inOrder(TreeNode* node) {      if (node == nullptr) return;      inOrder(node->left);      cout << node->data << " ";      inOrder(node->right);  }    // 后序遍历  void postOrder(TreeNode* node) {      if (node == nullptr) return;      postOrder(node->left);      postOrder(node->right);      cout << node->data << " ";  }    // 可视化打印树结构（直观展示层级）  void printTree(TreeNode* node, string prefix = "", bool isLeft = true) {      if (node == nullptr) return;      cout << prefix << (isLeft ? "├── " : "└── ") << node->data << endl;      printTree(node->left, prefix + (isLeft ? "│   " : "    "), true);      printTree(node->right, prefix + (isLeft ? "│   " : "    "), false);  }    // 释放树内存（后序遍历释放）  void deleteTree(TreeNode* node) {      if (node == nullptr) return;      deleteTree(node->left);      deleteTree(node->right);      delete node;  }    int main() {      // 层序遍历数组：表示一个4层二叉树      // 结构：      //        1      //       / \      //      2   3      //     / \ / \      //    4  5 6  7      //   /      //  8      // 注：数组中-1表示对应位置为空节点（示例中无空节点，仅展示格式）      vector<int> levelOrderNums = {1, 2, 3, 4, 5, 6, 7, 8};        // 递归构建树（从根节点索引0开始）      TreeNode* root = buildTreeRecursive(levelOrderNums, 0);        // 打印构建结果      cout << "递归构建的4层二叉树结构：" << endl;      printTree(root);      cout << endl;        // 遍历验证      cout << "先序遍历：";      preOrder(root);  // 输出：1 2 4 8 5 3 6 7      cout << endl;        cout << "中序遍历：";      inOrder(root);   // 输出：8 4 2 5 1 6 3 7      cout << endl;        cout << "后序遍历：";      postOrder(root); // 输出：8 4 5 2 6 7 3 1      cout << endl;        // 释放内存      deleteTree(root);      return 0;  }

运行结果：

二叉树链式存储结构：  ├── 1  │   ├── 2  │   │   ├── 4  │   │   └── 5  │   └── 3  │       └── 6  先序遍历（根→左→右）：1 2 4 5 3 6   中序遍历（左→根→右）：4 2 5 1 3 6   后序遍历（左→右→根）：4 5 2 6 3 1   非递归后序遍历：4 5 2 6 3 1