树的存储与遍历—链式存储
一、定义
链式存储是表示树结构最直观、最常用的一种方法。它的核心思想是：
用链表中的节点来表示树中的每个元素。每个节点不仅包含数据本身，还包含指向其子节点的指针。
二、基本结构
对于一个普通的树（不一定是二叉树），一个典型的链式存储节点结构如下：
// 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
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
