二叉树遍历数组存储的优势与不足

二叉树遍历数组存储的优势是：

1. 空间利用率高：相比于链式存储结构，数组存储结构不需要额外存储左右子树的指针，因此可以利用连续的存储空间存储一棵二叉树，从而节省存储空间。

2. 逻辑结构清晰：数组存储结构可以直观地表示出二叉树的逻辑结构，例如，根节点的下标为 0，它的左子节点下标为 1，右子节点下标为 2，而它的父节点下标为 (i-1)/2（其中 i 为节点下标）。

3. 遍历简便：由于数组存储结构直观地表示出了二叉树的逻辑结构，因此遍历二叉树时可以直接通过下标访问节点，不需要像链式存储结构一样需要通过指针进行访问。

二叉树遍历数组存储的不足是：

1. 插入删除操作复杂：由于数组存储结构是静态的，如果需要插入或删除节点，就需要重新构建数组，这样会导致操作的复杂度增加。

2. 空间浪费：如果二叉树的深度比较大，由于数组存储结构是连续的，因此会导致存储空间的浪费。

相关问题

数据结构二叉树C语言先序遍历数组

数据结构中的二叉树是一种非线性的数据组织形式，其中每个节点最多有两个子节点。先序遍历是指按照“根-左-右”的顺序访问二叉树中的所有节点。

在C语言中，如果我们把二叉树的节点信息存储在一个数组里来模拟这个过程，可以采用递归或栈的方式实现先序遍历。以下是简单的递归方法：

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

void preorderTraversal(int arr[], int size, int index = 0) {
    if (index < size) {
        // 先访问当前节点
        printf("%d ", arr[index]);
        
        // 再递归遍历左子树
        preorderTraversal(arr, size, index * 2 + 1);
        
        // 最后递归遍历右子树
        preorderTraversal(arr, size, index * 2 + 2);
    }
}

在这个数组表示法中，`arr[index]`代表当前节点，`arr[index * 2 + 1]`和`arr[index * 2 + 2]`分别代表左子节点和右子节点（假设二叉树的每个节点都有两个子节点）。如果某个节点没有右孩子，那么`arr[index * 2 + 2]`会被视为无效索引。

二叉树遍历（用结构体数组存储）算法

二叉树遍历可以通过结构体数组存储实现，具体算法步骤如下：

1. 定义二叉树的结构体，包括节点值、左子节点和右子节点。

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

2. 定义结构体数组，用于存储二叉树节点的值。

struct Node {
    int val;
    bool visited;
};

其中，visited 表示该节点是否已被访问过。

3. 创建二叉树，将结构体数组中的值存储到二叉树中。

TreeNode* createTree(Node* nodes, int n, int i) {
    if (i >= n || nodes[i].val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode();
    root->val = nodes[i].val;
    root->left = createTree(nodes, n, 2 * i + 1);
    root->right = createTree(nodes, n, 2 * i + 2);
    return root;
}

其中，n 表示结构体数组的长度，i 表示当前节点在结构体数组中的位置。

4. 中序遍历二叉树，将遍历结果存储到另一个结构体数组中。

void inOrder(TreeNode* root, Node* nodes, int& i) {
    if (!root) {
        return;
    }
    inOrder(root->left, nodes, i);
    nodes[i].val = root->val;
    nodes[i].visited = false;
    i++;
    inOrder(root->right, nodes, i);
}

其中，i 表示当前节点在结构体数组中的位置。

5. 实现遍历函数，通过结构体数组实现二叉树的遍历。

void traverse(Node* nodes, int n, TreeNode* root) {
    stack<TreeNode*> s;
    int i = 0;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (!node) {
            continue;
        }
        if (!nodes[i].visited) {
            cout << node->val << " ";
            nodes[i].visited = true;
        } else {
            s.push(node->right);
        }
        s.push(node);
        s.push(node->left);
        i++;
    }
}

其中，使用栈实现二叉树的遍历，节点访问的顺序与入栈的顺序相同，遍历过程中使用结构体数组记录每个节点是否已被访问过。

通过结构体数组存储二叉树，可以方便地实现对二叉树的遍历操作，并且可以避免指针操作带来的风险和复杂性。