二叉树的存储结构建立

二叉树是一种常见的树状数据结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的存储结构有多种方式，常见的有两种：链式存储和顺序存储。

1. 链式存储：
链式存储是通过节点之间的指针链接来表示二叉树的结构。每个节点包含三个部分：数据域、左子节点指针和右子节点指针。通过指针的链接，可以方便地遍历和操作二叉树。链式存储的优点是可以灵活地插入和删除节点，但是需要额外的指针空间。

2. 顺序存储：
顺序存储是使用数组来表示二叉树的结构。将二叉树的节点按照层次遍历的顺序依次存储在数组中，对于第i个节点，其左子节点存储在2i位置，右子节点存储在2i+1位置。顺序存储的优点是节省了指针空间，但是对于非完全二叉树会浪费一部分数组空间。

以上是二叉树的两种常见存储结构，具体选择哪种方式取决于实际需求和操作的复杂度。你可以根据具体情况选择适合的存储方式。

相关问题

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

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

#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` 函数，传入根结点指针的引用，即可完成二叉树的输入。

建立二叉树的二叉链表存储结构

二叉链表存储结构是指在二叉树的每个结点中，除了存储该结点的数据元素之外，还增加了两个指针，分别指向该结点的左子树和右子树。以下是建立二叉树的二叉链表存储结构的示例代码：

typedef struct BiTNode {
    int data; // 数据元素
    struct BiTNode *lchild, *rchild; // 左右子树指针
} BiTNode, *BiTree;

其中，`BiTNode` 是二叉树的结点类型，包含数据元素 `data` 和左右子树指针 `lchild` 和 `rchild`；`BiTree` 是指向二叉树根节点的指针类型。

二叉树的建立可以通过递归算法实现，具体代码如下：

// 先序遍历建立二叉树
void CreateBiTree(BiTree *T) {
    int data;
    scanf("%d", &data);
    if (data == 0) {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T) {
            exit(1); // 内存分配失败
        }
        (*T)->data = data;
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
}

该算法通过先序遍历的方式，依次读入二叉树的各个结点，如果读入的数据为 0，则表示该结点为空；否则，分配内存空间并存储数据元素，然后递归地建立它的左右子树。