C++ 算法：将顺序存储的数组转换为二叉链表

下面是一个将按顺序方式存储在数组中的二叉树转换为二叉链表形式的 C++ 算法：

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

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

void arrayToBinaryTree(TreeNode* &root, char* c, int n) {
    if (n <= 0) {
        root = NULL;
        return;
    }
    
    // 创建根节点
    root = new TreeNode(c[0]);
    
    // 使用队列辅助构建二叉树
    queue<TreeNode*> q;
    q.push(root);
    
    int i = 1;  // 数组下标
    while (!q.empty() && i < n) {
        TreeNode* node = q.front();
        q.pop();
        
        // 构建左子树
        if (c[i] != '.') {
            node->left = new TreeNode(c[i]);
            q.push(node->left);
        }
        i++;
        
        // 构建右子树
        if (i < n && c[i] != '.') {
            node->right = new TreeNode(c[i]);
            q.push(node->right);
        }
        i++;
    }
}

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    inorderTraversal(root->left);
    cout << root->val << ' ';
    inorderTraversal(root->right);
}

int main() {
    char c[] = {'A', 'B', 'C', '.', 'D', '.', 'E'};
    int n = sizeof(c) / sizeof(c[0]);
    
    TreeNode* root;
    arrayToBinaryTree(root, c, n);
    
    inorderTraversal(root);
    
    return 0;
}

运行结果：

B A D C E 

该算法首先根据数组的首元素创建根节点，然后使用队列辅助构建二叉树。在循环中，每次从队列中取出一个节点，根据数组的下一个元素构建其左子树，再根据数组的下一个元素构建其右子树。循环继续直到队列为空或者数组遍历完。最后，使用中序遍历验证二叉链表的正确性。