c++ 一维数组保存二叉树

一维数组保存二叉树是一种常见的数据结构存储方式。它将二叉树的节点按照从上到下、从左到右的顺序依次存储在数组中。

对于二叉树中的任意一个节点，如果它在数组中的下标为i，那么它的左孩子节点就在下标2i处，右孩子节点在下标2i+1处。这样的存储方式可以方便地进行遍历和搜索操作。

在利用一维数组保存二叉树时，需要特别注意数组下标和二叉树节点之间的转换关系，以及如何解决数组中空缺节点和二叉树中空指针的对应关系。

另外，由于数组是一种连续存储的数据结构，在保存二叉树时需要特别关注数组的长度和容量，确保能够存储足够的节点。当二叉树的节点数目超过数组的容量时，需要进行数组扩容操作。

总的来说，一维数组保存二叉树是一种简单高效的存储方式，能够方便地进行遍历、搜索和插入操作，但是在实际应用中需要综合考虑存储效率、空间利用和编程复杂度等因素。

相关问题

用一维数组存放完全二叉树

一维数组可以用来存放完全二叉树。完全二叉树是一种特殊的二叉树，它的每个节点都按照从上到下、从左到右的顺序依次排列。我们可以使用数组来表示完全二叉树，其中数组的索引表示节点的位置，数组的值表示节点的值。

具体的存储方式如下：
1. 对于完全二叉树中的第i个节点，它的左子节点的索引为2i，右子节点的索引为2i+1。
2. 对于完全二叉树中的第i个节点，它的父节点的索引为i/2（向下取整）。

下面是一个示例，演示如何使用一维数组存放完全二叉树，并实现先序、中序和后序遍历：

# 定义完全二叉树的一维数组表示
tree = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']

# 先序遍历
def preorder(root):
    if root <= len(tree) - 1:
        if tree[root] is not None:
            print(tree[root], end=' ')
            preorder(root * 2)  # 遍历左子树
            preorder(root * 2 + 1)  # 遍历右子树

# 中序遍历
def inorder(root):
    if root <= len(tree) - 1:
        if tree[root] is not None:
            inorder(root * 2)  # 遍历左子树
            print(tree[root], end=' ')
            inorder(root * 2 + 1)  # 遍历右子树

# 后序遍历
def postorder(root):
    if root <= len(tree) - 1:
        if tree[root] is not None:
            postorder(root * 2)  # 遍历左子树
            postorder(root * 2 + 1)  # 遍历右子树
            print(tree[root], end=' ')

# 演示先序、中序和后序遍历
print("先序遍历结果：")
preorder(1)
print("\n中序遍历结果：")
inorder(1)
print("\n后序遍历结果：")
postorder(1)

输出结果：

先序遍历结果：
A B D H I E J C F G 
中序遍历结果：
H D I B J E A F C G 
后序遍历结果：
H I D J E B F G C A 

c++ 数组建立二叉树

数组建立二叉树的方法是将二叉树按照完全二叉树的形式存储在数组中。具体步骤如下：

1. 将二叉树的根节点存放在数组的第一个位置，即a[1]。

2. 对于任意一个节点i，其左子节点的位置为2*i，右子节点的位置为2*i+1。

3. 若节点i的位置为j，则其父节点的位置为j/2（向下取整）。

4. 从第二个位置开始，依次输入二叉树的节点，若节点不存在则输入0。

例如，以下二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

可以用数组表示为：

a[1] = 1
a[2] = 2
a[3] = 3
a[4] = 4
a[5] = 5
a[6] = 6
a[7] = 7

其中，a[1]为根节点，a[2]和a[3]为其左右子节点，a[4]和a[5]为节点2的左右子节点，a[6]和a[7]为节点3的左右子节点。

建立二叉树的代码示例：

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *buildTree(int *a, int n, int i) {
    if (i > n || a[i] == 0) { // 超出数组范围或节点为空
        return NULL;
    }
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = a[i];
    root->left = buildTree(a, n, 2*i);
    root->right = buildTree(a, n, 2*i+1);
    return root;
}

int main() {
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(a) / sizeof(int) - 1;
    TreeNode *root = buildTree(a, n, 1);
    return 0;
}

其中，buildTree函数用于建立二叉树，参数a为表示二叉树的数组，n为数组长度，i为当前节点在数组中的位置。函数会根据数组中的数值创建节点，并递归创建其左右子树。最后返回根节点。在主函数中，先计算数组长度n，然后调用buildTree函数建立二叉树。