EA1-二叉树的数据结构定义¶

在C语言中，二叉树的实现主要有两种存储结构：链式存储和顺序存储。下面分别介绍它们的数据结构定义，并说明各自的优缺点和适用场景。

一、链式存储结构（常用）¶

链式结构使用指针动态构建二叉树节点，是最常见的二叉树实现方式。

1. 数据结构定义¶

C
typedef struct TreeNode {
    int data;                       // 数据域
    struct TreeNode* left;          // 左子树指针
    struct TreeNode* right;         // 右子树指针
} TreeNode;

2. 使用示例¶

C
// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(1);
    }
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

3. 特点¶

优点：
灵活，适合任意形状的二叉树（尤其是非完全二叉树）。
插入、删除操作方便。
缺点：
需要额外空间存储指针。
无法直接通过索引访问节点。

二、顺序存储结构（适用于完全二叉树）¶

顺序结构使用数组存储二叉树节点，通常用于完全二叉树或堆（Heap）结构。

1. 数据结构定义¶

C
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];     // 存储节点数据
    int count;              // 当前节点数量
} BinaryTree;

注：通常将根节点放在 data[1] 而不是 data[0]，以便利用下标关系：
若父节点在 i，则左孩子在 2*i，右孩子在 2*i+1。

2. 节点位置关系（基于1的索引）¶

节点位置	左孩子	右孩子	父节点
i	2i	2i+1	i/2

若使用0为起始索引，则： - 左孩子：2*i + 1 - 右孩子：2*i + 2 - 父节点：(i-1)/2

3. 示例（0起始索引）¶

C
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int count;
} BinaryTree;

// 初始化
void initTree(BinaryTree* tree) {
    tree->count = 0;
}

4. 特点¶

优点：
存储紧凑，访问速度快（随机访问）。
适合完全二叉树、堆、二叉查找树的数组实现（如堆排序）。
缺点：
对于普通二叉树会造成大量空间浪费（稀疏存储）。
插入删除效率低，需移动元素或预留空间。

三、扩展：带父指针的链式结构（可选）¶

若需要向上遍历，可增加父指针：

C
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    struct TreeNode* parent;  // 指向父节点
} TreeNode;

适用于需要回溯的场景（如二叉搜索树中找后继节点）。

四、对比总结¶

存储方式	适用场景	空间效率	时间效率	灵活性
链式	任意二叉树	中等（含指针开销）	高（动态）	高
顺序	完全/满二叉树、堆	高（密集）或低（稀疏）	高（随机访问）	低

✅ 推荐：链式存储用于一般二叉树（如BST、AVL、表达式树）；
✅ 推荐：顺序存储用于堆或完全二叉树。

五、可视化：链式 vs 顺序¶

graph TD
    A[Root] --> B[Left]
    A --> C[Right]
    B --> D[LL]
    B --> E[LR]

    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333
    style C fill:#bbf,stroke:#333

顺序存储数组表示（0起始索引）：

Text Only
1 2 3 4	`Index: 0 1 2 3 4 Data: [A, B, C, D, E] ↑ ↑ ↑ ↑ ↑ A B C D E`

其中：B(1) 的左孩子是 D(3)=21+1，右孩子是 E(4)=21+2

六、延伸知识点¶

堆（Heap）：通常用顺序存储实现完全二叉树。
线索二叉树：在链式结构中利用空指针指向中序前驱/后继，提高遍历效率。
静态链表：用数组模拟链式结构，结合两者优点。

如需实现遍历（前序、中序、后序、层序）、插入、删除等操作，也可继续扩展。是否需要？