建立二叉树的存储结构（层次次序）

二叉树的层次遍历是一种常用的遍历方式，也可以用于存储二叉树。具体来说，可以使用一个数组来存储二叉树的节点，按照二叉树的层次遍历顺序，依次将每个节点存入数组中。如果当前节点的左子节点存在，则存储在数组的下标为当前节点下标的 2 倍的位置上；如果当前节点的右子节点存在，则存储在数组的下标为当前节点下标的 2 倍加 1 的位置上。这种方式称为二叉树的顺序存储结构，常用于完全二叉树的存储。

例如，对于下面的二叉树：

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

其层次遍历序列为：1, 2, 3, 4, 5, 6, 7。对应的存储结构如下所示：

[1, 2, 3, 4, 5, 6, 7]

其中，下标为 0 的位置不存储节点。

相关问题

建立二叉树的存储结构（层次次序）代码

以下是使用 Python 实现二叉树的层次遍历存储结构的代码示例：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        
def create_tree(nums):
    if not nums:
        return None
    root = TreeNode(nums[0])
    queue = [root]
    i = 1
    while i < len(nums):
        curr = queue.pop(0)
        if nums[i] is not None:
            curr.left = TreeNode(nums[i])
            queue.append(curr.left)
        i += 1
        if i < len(nums) and nums[i] is not None:
            curr.right = TreeNode(nums[i])
            queue.append(curr.right)
        i += 1
    return root

其中，`create_tree` 函数接收一个列表 `nums`，表示二叉树的层次遍历序列。函数首先创建二叉树的根节点，然后使用一个队列 `queue` 来存储待处理的节点。从 `nums` 的第二个元素开始，依次遍历 `nums` 中的每个元素，如果当前元素不为空，则将其作为当前节点的左子节点或右子节点，然后将其加入队列中等待处理。函数最后返回二叉树的根节点。

建立二叉树存储结构的输入函数

二叉树的存储结构有很多种，以下是一种基于链式存储的二叉树输入函数的示例代码，希望能对您有所帮助：

#include <iostream>
using namespace std;

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

// 输入二叉树函数
void input(TreeNode* &root) {
    int val;
    cin >> val;
    if (val == -1) { // 如果输入 -1，表示当前结点为空
        root = NULL;
    } else {
        root = new TreeNode(val); // 新建结点
        input(root->left); // 递归输入左子树
        input(root->right); // 递归输入右子树
    }
}

int main() {
    TreeNode* root;
    cout << "请输入二叉树结点的值，以 -1 结束：" << endl;
    input(root);
    return 0;
}

在这段代码中，我们使用了一个输入函数 `input` 来构建二叉树。函数的输入参数是指向根结点的指针 `TreeNode* &root`，因为我们需要修改根结点的指向，所以使用引用。函数内部先读入一个整数 `val`，表示当前结点的值，如果 `val` 为 -1，则表示当前结点为空结点，将其指针赋为 NULL；否则，新建一个结点，并递归调用 `input` 函数输入左右子树。最后，在 `main` 函数中调用 `input` 函数，传入根结点指针的引用，即可完成二叉树的输入。