C语言 顺序二叉树的初始化

顺序二叉树是一种特殊的二叉树存储结构，可以用一维数组来表示。对于一个深度为n的二叉树，它的节点数最多为2^n-1个，因此可以用一个长度为2^n的数组来存储。假设数组下标从1开始，那么第i个节点的左孩子节点为2i，右孩子节点为2i+1，父节点为i/2。

顺序二叉树的初始化包括两个步骤：

1. 创建一个长度为n的数组，用于存储二叉树的节点数据。
2. 将数组中的所有元素初始化为一个特定的值，表示节点为空。

下面是C语言中顺序二叉树的初始化代码：

#define MAX_SIZE 100

typedef struct TreeNode {
    int data;
} TreeNode;

TreeNode tree[MAX_SIZE];

void initTree(int n) {
    for (int i = 0; i < n; i++) {
        tree[i].data = -1;   // 初始化为空节点
    }
}

这里定义了一个结构体TreeNode，用于表示二叉树的节点。数组tree用于存储二叉树的节点数据，数组大小为MAX_SIZE。函数initTree用于初始化二叉树，参数n表示二叉树的节点数，函数将数组中的所有元素初始化为-1，表示节点为空。

相关问题

c语言实现二叉树顺序存储以及基本操作

二叉树的顺序存储是将二叉树的节点按照从上到下、从左到右的顺序依次存放在一个数组中，这样可以方便地进行节点的访问和操作。其中，对于第 i 个节点，它的左子节点和右子节点分别存放在数组中的第 2*i 和 2*i+1 个位置上。

下面是c语言实现二叉树顺序存储以及基本操作的代码：

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

#define MAXSIZE 100

// 定义二叉树节点结构体
typedef struct TreeNode {
    char data;  // 节点数据
} TreeNode;

// 定义二叉树结构体
typedef struct BinaryTree {
    TreeNode nodes[MAXSIZE];  // 存储节点的数组
    int size;  // 当前节点数
} BinaryTree;

// 初始化二叉树
void init(BinaryTree *tree) {
    tree->size = 0;
}

// 生成新节点
TreeNode* newNode(char data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    return node;
}

// 在二叉树中插入新节点
void insert(BinaryTree *tree, char data) {
    if (tree->size >= MAXSIZE) {
        printf("Error: the binary tree is full!\n");
        return;
    }
    TreeNode *node = newNode(data);
    tree->nodes[++tree->size] = *node;
}

// 获取指定节点的左子节点
TreeNode* getLeftChild(BinaryTree *tree, int index) {
    int leftChildIndex = 2 * index;
    if (leftChildIndex > tree->size) {
        printf("Error: the node does not have left child!\n");
        return NULL;
    }
    return &tree->nodes[leftChildIndex];
}

// 获取指定节点的右子节点
TreeNode* getRightChild(BinaryTree *tree, int index) {
    int rightChildIndex = 2 * index + 1;
    if (rightChildIndex > tree->size) {
        printf("Error: the node does not have right child!\n");
        return NULL;
    }
    return &tree->nodes[rightChildIndex];
}

// 获取指定节点的父节点
TreeNode* getParent(BinaryTree *tree, int index) {
    if (index <= 1 || index > tree->size) {
        printf("Error: the node does not have parent!\n");
        return NULL;
    }
    return &tree->nodes[index/2];
}

// 打印节点的数据
void printNode(TreeNode *node) {
    printf("%c ", node->data);
}

// 先序遍历二叉树
void preOrderTraversal(BinaryTree *tree, int index) {
    if (index > tree->size) {
        return;
    }
    printNode(&tree->nodes[index]);
    preOrderTraversal(tree, 2*index);
    preOrderTraversal(tree, 2*index+1);
}

// 中序遍历二叉树
void inOrderTraversal(BinaryTree *tree, int index) {
    if (index > tree->size) {
        return;
    }
    inOrderTraversal(tree, 2*index);
    printNode(&tree->nodes[index]);
    inOrderTraversal(tree, 2*index+1);
}

// 后序遍历二叉树
void postOrderTraversal(BinaryTree *tree, int index) {
    if (index > tree->size) {
        return;
    }
    postOrderTraversal(tree, 2*index);
    postOrderTraversal(tree, 2*index+1);
    printNode(&tree->nodes[index]);
}

int main() {
    BinaryTree tree;
    init(&tree);

    insert(&tree, 'A');
    insert(&tree, 'B');
    insert(&tree, 'C');
    insert(&tree, 'D');
    insert(&tree, 'E');

    printf("preOrderTraversal: ");
    preOrderTraversal(&tree, 1);
    printf("\n");

    printf("inOrderTraversal: ");
    inOrderTraversal(&tree, 1);
    printf("\n");

    printf("postOrderTraversal: ");
    postOrderTraversal(&tree, 1);
    printf("\n");

    return 0;
}

在上面的代码中，我们定义了一个 `BinaryTree` 结构体，其中包含了一个 `TreeNode` 类型的数组 `nodes` 来存储节点，还有一个 `size` 变量来记录当前节点数。同时，我们还定义了几个函数来实现二叉树的基本操作，例如插入新节点、获取子节点和父节点、遍历等等。最后，在 `main` 函数中，我们向二叉树中插入了 5 个节点，并分别进行了先序、中序和后序遍历。

c语言实现二叉树按层遍历

在 C 语言中实现二叉树的按层遍历，通常采用队列（Queue）数据结构，因为队列的特性正好适合这种逐层访问的顺序。这里提供一个基于广度优先搜索（BFS）的简单实现：

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

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

// 创建一个新的二叉树节点
TreeNode* newNode(int val) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 按层遍历函数
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    
    // 初始化队列并添加根节点
    Queue queue;
    enqueue(&queue, root);
    
    while (!isQueueEmpty(&queue)) {
        // 弹出队首元素
        TreeNode* temp = dequeue(&queue);
        
        // 输出当前节点值
        printf("%d ", temp->val);
        
        // 如果有左、右子节点，添加到队列中
        if (temp->left != NULL) enqueue(&queue, temp->left);
        if (temp->right != NULL) enqueue(&queue, temp->right);
    }
}

// 队列操作，这里假设已经定义了enqueue和dequeue函数
void enqueue(Queue* queue, TreeNode* node) {
    // ...
}
int isQueueEmpty(Queue* queue) {
    // ...
}

// 主函数示例
int main() {
    // 构建二叉树（例如：创建一个简单的二叉树）
    TreeNode* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Level order traversal of the binary tree: ");
    levelOrderTraversal(root);
    return 0;
}