构造利用二叉链表储存的二叉树

在二叉链表中，每个结点都包含三个域：数据域，左孩子指针域和右孩子指针域。构造二叉树的基本思路是按照先序遍历的顺序读入二叉树中的结点信息，并根据读入的信息构造出对应的二叉链表。

具体构造过程如下：

1. 创建一个空的二叉链表根节点，即指向根节点的指针为空。

2. 读入下一个结点的数据，如果该结点是空节点，则将其设置为NULL，否则创建一个新的二叉链表结点，并将该结点的数据存入数据域中。

3. 如果当前结点不是空节点，则读入其左子树结点的数据，按照步骤2的方法创建左子树结点，并将该结点的指针赋值给当前结点的左孩子指针域。

4. 如果当前结点不是空节点，则读入其右子树结点的数据，按照步骤2的方法创建右子树结点，并将该结点的指针赋值给当前结点的右孩子指针域。

5. 如果当前结点是空节点，则返回上一层递归。

6. 重复步骤2到5，直到所有的结点都被读入并创建出来。

下面是一个示例代码，用于构造一个二叉树：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void buildTree(TreeNode* &root) {
    int val;
    cin >> val;
    if (val == -1) {
        root = NULL;
        return;
    }
    root = new TreeNode(val);
    buildTree(root->left);
    buildTree(root->right);
}

int main() {
    TreeNode* root;
    cout << "请输入二叉树的先序遍历序列，并以-1表示空节点：" << endl;
    buildTree(root);
    return 0;
}

在示例代码中，我们定义了一个名为`TreeNode`的结构体用于表示二叉链表结点，其中包含一个`val`数据域和两个指针域`left`和`right`。`buildTree`函数用于递归构造二叉树，其中通过读入输入的方式获取二叉树的先序遍历序列，并按照上述构造过程创建二叉链表结点。最后，我们将构造好的二叉树的根节点存入指针变量`root`中。