二叉树的顺序存储及基本操作

二叉树的顺序存储是指将二叉树按照层次顺序依次存储到数组中，具体操作如下：

1. 数组下标从1开始，根节点存储在下标为1的位置。

2. 对于下标为i的节点，其左子节点存储在下标为2i的位置，右子节点存储在下标为2i+1的位置。

3. 若一个节点没有子节点，则对应下标位置的值为0或NULL。

基本操作包括：

1. 创建二叉树：按照层次顺序依次输入节点的值，将其存储到数组中。

2. 遍历二叉树：包括前序遍历、中序遍历和后序遍历。

3. 查找节点：根据节点的值在数组中查找其对应的下标位置。

4. 插入节点：在数组中找到插入位置，将节点的值存储到相应的位置。

5. 删除节点：将节点对应的下标位置的值设为0或NULL。

需要注意的是，二叉树的顺序存储方式只适用于完全二叉树，对于非完全二叉树会浪费很多空间。

相关问题

touge 二叉树的顺序存储及基本操作

二叉树的顺序存储也叫做顺序表存储，指的是将二叉树的结点按照某种顺序存储在一维数组中，然后通过数组下标来访问结点。假设二叉树的深度为d，那么顺序存储需要的数组大小为$2^d-1$，其中，下标为i的结点的左孩子结点下标为$2i+1$，右孩子结点下标为$2i+2$，父结点下标为$(i-1)/2$。

下面是二叉树的顺序存储实现及基本操作的代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 二叉树的顺序存储
class SeqBinaryTree {
public:
    SeqBinaryTree(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return;
        data_ = vector<TreeNode*>(n, NULL);
        for (int i = 0; i < n; i++) {
            if (nums[i] != -1) {
                data_[i] = new TreeNode(nums[i]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (data_[i] != NULL) {
                int left = i * 2 + 1, right = i * 2 + 2;
                if (left < n) data_[i]->left = data_[left];
                if (right < n) data_[i]->right = data_[right];
            }
        }
    }

    // 获取根结点
    TreeNode* getRoot() {
        return data_[0];
    }

    // 获取结点数
    int size() {
        return data_.size();
    }

private:
    vector<TreeNode*> data_;
};

int main() {
    vector<int> nums = {1, 2, 3, -1, -1, 4, 5};
    SeqBinaryTree tree(nums);
    cout << "size: " << tree.size() << endl;
    cout << "root: " << tree.getRoot()->val << endl;
    return 0;
}

上述代码中，我们通过一个vector来存储二叉树的结点，其中，如果某个结点为空，我们用NULL表示。在构造函数中，我们遍历vector，将不为空的结点存储在数组中，并为每个结点的左右孩子指针赋值。在getroot()函数中，我们返回数组的第一个元素，即根结点。在size()函数中，我们返回数组的大小，即为二叉树的结点数。

除了上述基本操作外，我们还可以实现其他操作，比如获取某个结点的左孩子、右孩子、父结点等，这些操作的实现方法与普通二叉树类似。

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 个节点，并分别进行了先序、中序和后序遍历。