二叉链表创建二叉树

二叉链表是一种二叉树的链式存储结构，每个节点包含两个指针：一个指向左子树，另一个指向右子树。创建一棵二叉树可以通过先创建一个二叉链表，然后将其转化为二叉树的形式。

下面是二叉链表创建二叉树的步骤：

1. 创建二叉链表节点结构体，包含左右子树指针和节点值。

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

2. 以先序遍历的方式输入节点的值，若输入字符 '#'，则表示该节点为空。

TreeNode* createBinaryTree() {
    char ch;
    cin >> ch;
    if (ch == '#') {
        return NULL;
    }
    TreeNode* root = new TreeNode(ch - '0');
    root->left = createBinaryTree();
    root->right = createBinaryTree();
    return root;
}

3. 调用createBinaryTree()函数，得到根节点指针。

TreeNode* root = createBinaryTree();

4. 将二叉链表转化为二叉树，方法是使用队列，从根节点开始，依次出队节点，将其左右子节点入队，直到队列为空。每次出队的节点，将其左右子节点挂载到该节点上。

void convertToBinaryTree(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
        node->left = q.empty() ? NULL : q.front();
        node->right = q.empty() ? NULL : q.front()->right;
    }
}

完整代码如下：

#include <iostream>
#include <queue>
using namespace std;

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

TreeNode* createBinaryTree() {
    char ch;
    cin >> ch;
    if (ch == '#') {
        return NULL;
    }
    TreeNode* root = new TreeNode(ch - '0');
    root->left = createBinaryTree();
    root->right = createBinaryTree();
    return root;
}

void convertToBinaryTree(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
        node->left = q.empty() ? NULL : q.front();
        node->right = q.empty() ? NULL : q.front()->right;
    }
}

int main() {
    TreeNode* root = createBinaryTree();
    convertToBinaryTree(root);
    return 0;
}