侧边栏壁纸
博主头像
MindPalette 博主等级

行动起来，活在当下

  • 累计撰写 108 篇文章
  • 累计创建 31 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录
C 数据结构

二叉树的存储

~梓
~梓
2025-09-22 / 0 评论 / 0 点赞 / 4 阅读 / 0 字
温馨提示：
部分素材来自网络，若不小心影响到您的利益，请联系我们删除。

二叉树的顺序存储

一、为什么需要顺序存储二叉树？

在数据结构里，二叉树的存储方式有两种：链式存储和顺序存储。链式存储用指针串联节点，灵活但对初学者不太友好；顺序存储用数组存放节点，通过下标计算节点关系，实现简单，尤其适合完全二叉树 —— （比如堆排序里的堆就是完全二叉树的顺序存储）。

顺序存储的核心思路：把二叉树的节点按层序遍历的顺序放进数组，根节点放第一个位置，然后依次是左孩子、右孩子，以此类推。通过下标公式，能快速找到任意节点的父节点和子节点，不需要指针。

二、C 语言实现代码

#include <stdio.h>
#include <string.h>

// 定义最大节点数（一般给固定大小，这里设为100足够用）
#define MAX_SIZE 100

// 二叉树的顺序存储结构
typedef struct {
    char data[MAX_SIZE];  // 存储节点数据（用char举例，也常考字符或整数）
    int length;           // 当前节点个数
} SeqBinTree;

// 1. 初始化二叉树
void InitTree(SeqBinTree *tree) {
    // 把数组清空，用'\0'表示空节点
    memset(tree->data, '\0', sizeof(tree->data));
    tree->length = 0;  // 初始节点数为0
}

// 2. 插入节点（按层序顺序插入，适合构建完全二叉树）
void InsertNode(SeqBinTree *tree, char data) {
    if (tree->length >= MAX_SIZE) {
        printf("树已满，无法插入\n");
        return;
    }
    // 新节点放在数组末尾（层序顺序）
    tree->data[tree->length] = data;
    tree->length++;
}

// 3. 求父节点（已知子节点下标i）
char GetParent(SeqBinTree *tree, int i) {
    if (i == 0) {  // 根节点（下标0）没有父节点
        return '\0';
    }
    // 父节点下标公式：(i-1)/2（整数除法）
    int parent_idx = (i - 1) / 2;
    return tree->data[parent_idx];
}

// 4. 求左孩子（已知父节点下标i）
char GetLeftChild(SeqBinTree *tree, int i) {
    // 左孩子下标公式：2*i + 1
    int left_idx = 2 * i + 1;
    // 下标超出范围，说明没有左孩子
    if (left_idx >= tree->length) {
        return '\0';
    }
    return tree->data[left_idx];
}

// 5. 求右孩子（已知父节点下标i）
char GetRightChild(SeqBinTree *tree, int i) {
    // 右孩子下标公式：2*i + 2
    int right_idx = 2 * i + 2;
    if (right_idx >= tree->length) {
        return '\0';
    }
    return tree->data[right_idx];
}

// 6. 前序遍历（递归版，
高频考点）
// 顺序：根节点 -> 左子树 -> 右子树
void PreOrder(SeqBinTree *tree, int i) {
    // 下标越界，说明是空节点，递归结束
    if (i >= tree->length) {
        return;
    }
    // 访问当前节点
    printf("%c ", tree->data[i]);
    // 遍历左子树（左孩子下标：2*i+1）
    PreOrder(tree, 2*i + 1);
    // 遍历右子树（右孩子下标：2*i+2）
    PreOrder(tree, 2*i + 2);
}

// 7. 中序遍历（递归版）
// 顺序：左子树 -> 根节点 -> 右子树
void InOrder(SeqBinTree *tree, int i) {
    if (i >= tree->length) {
        return;
    }
    InOrder(tree, 2*i + 1);    // 左
    printf("%c ", tree->data[i]);  // 根
    InOrder(tree, 2*i + 2);    // 右
}

// 8. 后序遍历（递归版）
// 顺序：左子树 -> 右子树 -> 根节点
void PostOrder(SeqBinTree *tree, int i) {
    if (i >= tree->length) {
        return;
    }
    PostOrder(tree, 2*i + 1);  // 左
    PostOrder(tree, 2*i + 2);  // 右
    printf("%c ", tree->data[i]);  // 根
}

// 9. 层序遍历（顺序存储的天然优势，直接按数组顺序输出）
void LevelOrder(SeqBinTree *tree) {
    for (int i = 0; i < tree->length; i++) {
        printf("%c ", tree->data[i]);
    }
}

// 主函数：测试以上功能
int main() {
    SeqBinTree tree;
    InitTree(&tree);

    // 构建一个完全二叉树
    // 结构如下：
    //       A
    //      / \
    //     B   C
    //    / \ /
    //   D  E F
    InsertNode(&tree, 'A');  // 下标0（根）
    InsertNode(&tree, 'B');  // 下标1（A的左孩子）
    InsertNode(&tree, 'C');  // 下标2（A的右孩子）
    InsertNode(&tree, 'D');  // 下标3（B的左孩子）
    InsertNode(&tree, 'E');  // 下标4（B的右孩子）
    InsertNode(&tree, 'F');  // 下标5（C的左孩子）

    // 测试父子关系
    printf("B的父节点：%c\n", GetParent(&tree, 1));  // 应该是A
    printf("C的左孩子：%c\n", GetLeftChild(&tree, 2)); // 应该是F
    printf("B的右孩子：%c\n", GetRightChild(&tree, 1));// 应该是E

    // 测试遍历
    printf("\n前序遍历：");
    PreOrder(&tree, 0);  // 预期：A B D E C F

    printf("\n中序遍历：");
    InOrder(&tree, 0);   // 预期：D B E A F C

    printf("\n后序遍历：");
    PostOrder(&tree, 0); // 预期：D E B F C A

    printf("\n层序遍历：");
    LevelOrder(&tree);   // 预期：A B C D E F

    return 0;
}

三、代码分析（重点看这里）

1. 结构体设计

typedef struct {
    char data[MAX_SIZE];
    int length;
} SeqBinTree;
  • data数组：按层序顺序存放节点，下标 0 是根节点，依次往后是第二层左、右孩子，第三层左左、左右、右左、右右……
  • length：记录实际节点数，方便判断是否越界（常考边界条件，比如空树、满树）。

2. 核心公式（必须记住）

顺序存储的灵魂是下标计算：

  • 若父节点下标为 i：
    • 左孩子下标 = 2*i + 1
    • 右孩子下标 = 2*i + 2
  • 若子节点下标为 i：
    • 父节点下标 = (i-1)/2（整数除法，比如 i=4 时，(4-1)/2=1，对应父节点下标 1）

3. 遍历方法（算法题核心）

四种遍历中，前、中、后序用递归实现（递归版），层序遍历直接按数组顺序输出（顺序存储的优势）。

以中序遍历为例，逻辑是 “左 - 根 - 右”：

void InOrder(SeqBinTree *tree, int i) {
    if (i >= tree->length) return;  // 递归终止条件
    InOrder(tree, 2*i + 1);    // 先遍历左子树
    printf("%c ", tree->data[i]);  // 再访问根节点
    InOrder(tree, 2*i + 2);    // 最后遍历右子树
}

递归终止条件是 “下标越界”，这是初学者容易漏掉的点，写算法必须包含。

四、扩展思考

  1. 适用场景：顺序存储只适合完全二叉树，否则会浪费空间（比如斜树，数组里会有很多空位）。可能问 “为什么堆要用顺序存储？”—— 因为堆是完全二叉树，顺序存储效率高。
  2. 与链式存储的对比：顺序存储找父子节点快（O (1)），但插入删除不方便；链式存储反之。简答题可能考这个对比。
  3. 常见错误：计算下标时忘记 “根节点从 0 开始”，比如误把左孩子公式写成 2*i（这是根节点从 1 开始的情况）。代码里严格用 0 开始，符合 C 语言数组习惯。

二叉树的链式存储

一、为什么用链式存储？

二叉树的链式存储用指针将节点串联起来，每个节点记录自己的左右孩子位置，不用像顺序存储那样考虑数组下标，对各种形态的二叉树都很友好。比如一棵不规则的二叉树（有的节点只有左孩子，有的只有右孩子），用链式存储不会浪费空间，插入删除也更方便，这也是它在考试和实际应用中更常见的原因。

二、C 语言实现代码

下面是适合初学者的代码，操作都很基础，注释详细，跟着实现一遍就能明白核心逻辑：

#include <stdio.h>
#include <stdlib.h>

// 节点结构体（考试中最常用的定义方式）
typedef struct Node {
    char data;               // 节点存储的数据（字符为例，也可以是整数等）
    struct Node *left;       // 左孩子指针
    struct Node *right;      // 右孩子指针
} Node;

// 创建新节点（基础操作，必须掌握）
Node* createNode(char data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->left = NULL;    // 初始时左右孩子都为空
    newNode->right = NULL;
    return newNode;
}

// 前序遍历（根→左→右，考试常考递归实现）
void preOrder(Node *root) {
    if (root == NULL) {      // 空节点则返回，递归终止条件
        return;
    }
    printf("%c ", root->data);  // 访问根节点
    preOrder(root->left);       // 遍历左子树
    preOrder(root->right);      // 遍历右子树
}

// 中序遍历（左→根→右）
void inOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);        // 先遍历左子树
    printf("%c ", root->data);  // 再访问根节点
    inOrder(root->right);       // 最后遍历右子树
}

// 后序遍历（左→右→根）
void postOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);      // 遍历左子树
    postOrder(root->right);     // 遍历右子树
    printf("%c ", root->data);  // 最后访问根节点
}

// 查找节点（根据值查找，辅助功能）
Node* findNode(Node *root, char target) {
    if (root == NULL) {
        return NULL;  // 树空或没找到
    }
    if (root->data == target) {
        return root;  // 找到目标节点
    }
    // 先在左子树找，找到就返回
    Node *leftResult = findNode(root->left, target);
    if (leftResult != NULL) {
        return leftResult;
    }
    // 左子树没找到，再在右子树找
    return findNode(root->right, target);
}

// 给指定节点添加左孩子
void addLeftChild(Node *parent, char data) {
    if (parent == NULL) {
        printf("父节点不存在，无法添加左孩子\n");
        return;
    }
    if (parent->left != NULL) {
        printf("左孩子已存在，无法添加\n");
        return;
    }
    parent->left = createNode(data);
}

// 给指定节点添加右孩子
void addRightChild(Node *parent, char data) {
    if (parent == NULL) {
        printf("父节点不存在，无法添加右孩子\n");
        return;
    }
    if (parent->right != NULL) {
        printf("右孩子已存在，无法添加\n");
        return;
    }
    parent->right = createNode(data);
}

// 释放二叉树内存（避免内存泄漏，好习惯）
void freeTree(Node *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);   // 先释放左子树
    freeTree(root->right);  // 再释放右子树
    free(root);             // 最后释放当前节点
}

int main() {
    // 手动构建一棵示例二叉树：
    //       A
    //      / \
    //     B   C
    //    /   / \
    //   D   E   F
  
    // 创建根节点
    Node *root = createNode('A');
  
    // 给根节点添加左右孩子
    addLeftChild(root, 'B');
    addRightChild(root, 'C');
  
    // 找到B节点，给它添加左孩子D
    Node *nodeB = findNode(root, 'B');
    addLeftChild(nodeB, 'D');
  
    // 找到C节点，给它添加左右孩子E和F
    Node *nodeC = findNode(root, 'C');
    addLeftChild(nodeC, 'E');
    addRightChild(nodeC, 'F');
  
    // 测试遍历（考试中最常考的内容）
    printf("前序遍历：");
    preOrder(root);  // 预期：A B D C E F
  
    printf("\n中序遍历：");
    inOrder(root);   // 预期：D B A E C F
  
    printf("\n后序遍历：");
    postOrder(root); // 预期：D B E F C A
  
    // 释放内存
    freeTree(root);
    return 0;
}

三、代码分析

1. 核心结构体设计

typedef struct Node {
    char data;
    struct Node *left;
    struct Node *right;
} Node;
0
C 数据结构
版权归属： ~梓
本文链接： https://www.serenova.cn/archives/er-cha-shu-de-cun-chu
许可协议： 本文使用《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》协议授权

评论区