C语言将一维数组转换成二叉树

createh51周前 (05-15)技术教程5

以下是C语言实现将一维数组转换为二叉树的代码：

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

// 定义二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 队列节点结构（用于层序遍历构建二叉树）
typedef struct QueueNode {
    struct TreeNode *treeNode;
    struct QueueNode *next;
} QueueNode;

// 队列结构
typedef struct {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// 创建空队列
Queue* createQueue() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// 入队操作
void enqueue(Queue *q, struct TreeNode *treeNode) {
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队操作
struct TreeNode* dequeue(Queue *q) {
    if (q->front == NULL) return NULL;
    
    QueueNode *temp = q->front;
    struct TreeNode *node = temp->treeNode;
    q->front = q->front->next;
    
    if (q->front == NULL)
        q->rear = NULL;
    
    free(temp);
    return node;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == NULL;
}

// 释放队列内存
void freeQueue(Queue *q) {
    if (!q) return;
    QueueNode *current = q->front;
    while (current) {
        QueueNode *temp = current;
        current = current->next;
        free(temp);
    }
    free(q);
}

// 核心函数：将数组转换为二叉树
struct TreeNode* arrayToTree(int* arr, int size, int nullValue) {
    if (size == 0 || arr[0] == nullValue) return NULL;
    
    // 创建根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = arr[0];
    root->left = root->right = NULL;
    
    Queue *q = createQueue();
    enqueue(q, root);
    
    int index = 1; // 从数组的第二个元素开始处理
    
    while (!isEmpty(q)) {
        struct TreeNode* current = dequeue(q);
        
        // 处理左子节点
        if (index < size) {
            if (arr[index] != nullValue) {
                struct TreeNode* leftNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                leftNode->val = arr[index];
                leftNode->left = leftNode->right = NULL;
                current->left = leftNode;
                enqueue(q, leftNode);
            }
            index++;
        }
        
        // 处理右子节点
        if (index < size) {
            if (arr[index] != nullValue) {
                struct TreeNode* rightNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                rightNode->val = arr[index];
                rightNode->left = rightNode->right = NULL;
                current->right = rightNode;
                enqueue(q, rightNode);
            }
            index++;
        }
    }
    
    freeQueue(q);
    return root;
}

// 层序遍历打印二叉树（测试用）
void printTree(struct TreeNode* root) {
    if (!root) {
        printf("Tree is empty.\n");
        return;
    }
    
    Queue *q = createQueue();
    enqueue(q, root);
    
    while (!isEmpty(q)) {
        struct TreeNode* current = dequeue(q);
        if (current) {
            printf("%d ", current->val);
            enqueue(q, current->left);
            enqueue(q, current->right);
        } else {
            printf("null ");
        }
    }
    freeQueue(q);
    printf("\n");
}

int main() {
    // 示例数组：-1表示空节点
    int arr[] = {1, 2, 3, -1, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int nullValue = -1;
    
    struct TreeNode* root = arrayToTree(arr, size, nullValue);
    printTree(root);
    
    return 0;
}

代码讲解

数据结构定义

TreeNode：二叉树节点，包含值和左右子节点指针。
QueueNode 和 Queue：用于层序遍历构建二叉树的队列结构。

队列操作

createQueue：创建空队列。
enqueue：将树节点加入队列尾部。
dequeue：从队列头部取出树节点并释放队列节点内存。
isEmpty：判断队列是否为空。
freeQueue：释放队列占用的所有内存。

核心函数 arrayToTree

输入：整型数组、数组长度、空节点标记值。

处理流程：

创建根节点并初始化队列。
循环处理队列中的每个节点：
从数组中取出元素创建左子节点（若非空），并加入队列。
从数组中取出下一个元素创建右子节点（若非空），并加入队列。
处理完所有数组元素后释放队列内存。

参数：

arr：输入的一维数组指针，按层序存储节点值。
size：数组的长度。
nullValue：表示空节点的特殊值（如 -1）。

返回值：二叉树的根节点指针。

arrayToTree详细说明：

1. 空数组或根节点为空的处理

if (size == 0 || arr[0] == nullValue) 
   return NULL;

作用：若数组为空或根节点值为空（如 arr[0] == -1），直接返回 NULL。
关键点：避免无效输入导致后续操作出错。

2. 创建根节点

struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = arr[0];
root->left = root->right = NULL;

步骤：
为根节点分配内存。
将数组第一个元素赋值给根节点的值（arr[0]）。
初始化左右子节点为 NULL。
意义：根节点是构建二叉树的起点。

3. 初始化队列

Queue *q = createQueue();
enqueue(q, root);
int index = 1; // 从数组的第二个元素开始处理

作用：
创建空队列 q，用于层序遍历。
将根节点入队，开始处理其子节点。
初始化索引 index 为 1，表示从数组第二个元素开始处理。
队列的意义：确保按层序逐个处理节点，维护父子关系。

4. 主循环：处理队列中的每个节点

while (!isEmpty(q)) {
    struct TreeNode* current = dequeue(q);

循环条件：队列非空时继续处理。
操作：

从队列头部取出节点 current（按层序处理）。

关键点：队列中存储的是待处理子节点的父节点。

5. 处理左子节点

if (index < size) {
    if (arr[index] != nullValue) {
        struct TreeNode* leftNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        leftNode->val = arr[index];
        leftNode->left = leftNode->right = NULL;
        current->left = leftNode;
        enqueue(q, leftNode);
    }
    index++;
}

步骤：
检查数组是否越界（index < size）。
若当前元素非空值：

为左子节点分配内存。
将数组元素赋值给左子节点的值。
将左子节点挂载到 current 的左侧。
左子节点入队，等待后续处理其子节点。

无论是否创建左子节点，index 递增。
意义：

按层序填充左子节点。
空节点（如 -1）不会创建节点，直接跳过。

6. 处理右子节点

if (index < size) {
    if (arr[index] != nullValue) {
        struct TreeNode* rightNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        rightNode->val = arr[index];
        rightNode->left = rightNode->right = NULL;
        current->right = rightNode;
        enqueue(q, rightNode);
    }
    index++;
}

逻辑：与处理左子节点完全对称。
关键点：

右子节点紧跟在左子节点之后处理。
同一父节点的左右子节点在数组中连续存储。

7. 循环结束与队列释放

freeQueue(q);
return root;

作用：

释放队列占用的内存。

返回构建好的二叉树的根节点。

内存管理：避免内存泄漏，确保队列被正确销毁。

关键逻辑总结

层序构建：

队列确保按层序处理节点。

父节点出队时，按顺序处理其左右子节点。

索引递增：

每个元素（包括空值）都会消耗索引，确保顺序正确。

空节点处理：

遇到 nullValue 时跳过节点创建，不挂载子节点。

时间复杂度：

遍历数组一次，时间复杂度为 O(n)，n 为数组长度。

示例解析

以数组 [1, 2, 3, -1, 4, 5] 为例：

根节点 1 入队。
出队 1，处理其左子节点 2 和右子节点 3，二者入队。
出队 2，处理左子节点（-1，跳过）和右子节点 4，4 入队。
出队 3，处理左子节点 5（右子节点超出数组长度，跳过），5 入队。
最终队列为空，构建完成。

输出：构建好的二叉树根节点指针。
测试函数 printTree

使用层序遍历打印二叉树，空节点输出"null"。

示例运行

示例数组 [1, 2, 3, -1, 4, 5] 对应二叉树结构：

关键点说明

层序构建：使用队列确保按照层序逐个处理节点，符合数组的存储顺序。
空节点处理：遇到空节点标记值时跳过创建子节点。
内存管理：在构建过程中及时释放队列内存，防止内存泄漏。

此代码能够正确地将层序排列的数组转换为二叉树结构，并通过测试函数验证结果。

C语言一维数组，到底是什么一回事?细细道来

一维数组定义和使用一维数组的定义格式如下：数据类型数组名 [常量值];格式分析：(1) 数据类型，表示要在数组中，存放数据的类型。例如，要存放整数值，可以是int类型；要存放字符，可以是char类型...

原来C语言多维数组这么好玩!带你轻松拿捏

程序员Feri一名12年+的程序员,做过开发带过团队创过业,擅长Java、鸿蒙、嵌入式、人工智能等开发,专注于程序员成长的那点儿事,希望在成长的路上有你相伴！君志所向,一往无前！在C语言的世界里，多维...

C语言-闲聊一维、二维数组

①若a[i]为一维数组则有，a[0]，为数组的一个元素。a[i]=*(&a[i])，为数组的一个元素。a+i=&a[i]，为元素a[i]的地址。*(*（a+i）)＝*(*&a[...

C语言中的一维数组理解

在C语言中，数组作为一种最常见的数据集，它属于C语言类型定义的构造类型，它中间的每一个成员类型完全一致，也就是说只要一定义了一维数组的数据类型，那么，它中间的元素就必须全部是这种类型，在数组中，所有...

60.一维数组的应用讲解VB中一维数组的应用。

任务实施2：计算一个班级45名学生的语文考试成绩的平均分。它给出的界面是单击输入，单击输入计算按钮就会弹出输入框，请输入第几位学生的语文成绩。输完语文成绩之后会弹出一个消息框显示语文成绩的平均分。这是...

大话C语言:数组

1 数组概述数组是若干个相同类型的变量在内存中有序存储的集合。数组是 C 语言中的一种数据结构，用于存储一组具有相同数据类型的数据。数组在内存中会开辟一块连续的空间数组中的每个元素可以通过一个索引（下...

勋勋教程网