C++ 算法：将数组存储的二叉树转换为二叉链表（不使用队列）

下面是一个将按顺序方式存储在数组中的二叉树转换为二叉链表形式的算法：\n\nc++\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nstruct TreeNode {\n char val;\n TreeNode* left;\n TreeNode* right;\n TreeNode(char x) : val(x), left(NULL), right(NULL) {}\n};\n\nTreeNode* convertToBinaryTree(char* c, int n) {\n if (n == 0) return NULL;\n\n vector<TreeNode*> nodes(n, NULL);\n for (int i = 0; i < n; i++) {\n if (c[i] != '.') {\n nodes[i] = new TreeNode(c[i]);\n }\n }\n\n int j = 1;\n for (int i = 0; i < n && j < n; i++) {\n if (nodes[i] != NULL) {\n nodes[i]->left = nodes[j++];\n if (j < n) {\n nodes[i]->right = nodes[j++];\n }\n }\n }\n\n return nodes[0];\n}\n\nvoid inorderTraversal(TreeNode* root) {\n if (root == NULL) return;\n\n inorderTraversal(root->left);\n cout << root->val << " ";\n inorderTraversal(root->right);\n}\n\nint main() {\n char c[] = {'A', 'B', 'C', '.', 'D', '.', '.', 'E'};\n int n = sizeof(c) / sizeof(c[0]);\n TreeNode* root = convertToBinaryTree(c, n);\n inorderTraversal(root);\n\n return 0;\n}\n\n\n在这个算法中，我们首先创建一个大小为n的节点数组nodes，并将数组中的非空字符创建为对应的节点。然后，我们使用两个指针i和j来遍历节点数组，将每个节点的左子节点和右子节点指向数组中的下一个节点。最后，我们返回根节点。\n\n在main函数中，我们创建一个测试数组c，并将其转换为二叉链表形式。然后，我们使用中序遍历来打印二叉链表的节点值。\n\n输出结果为：B A D C E，表示二叉链表的中序遍历结果。\n\n注意：这个算法假设输入的数组中的节点按照从上到下、从左到右的顺序存储，并且空节点用.表示。