c语言,用顺序存储结构来存储一颗具有n个结点的二叉树,
时间: 2023-06-13 10:07:53 浏览: 49
可以用一个一维数组来存储二叉树。假设二叉树的根节点在数组中的下标为0,则对于任意一个下标为i的节点,它的左子节点在下标2*i+1的位置,右子节点在2*i+2的位置。
具体实现代码如下:
```c
#define MAXSIZE 100 // 定义数组的最大长度
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createTree(int* nums, int n) {
if (n == 0) return NULL;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = nums[0];
root->left = root->right = NULL;
TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * MAXSIZE);
int front = 0, rear = 0;
queue[rear++] = root;
for (int i = 1; i < n; i += 2) {
TreeNode *cur = queue[front++];
if (nums[i] != -1) {
TreeNode *left = (TreeNode*)malloc(sizeof(TreeNode));
left->val = nums[i];
left->left = left->right = NULL;
cur->left = left;
queue[rear++] = left;
}
if (i + 1 < n && nums[i+1] != -1) {
TreeNode *right = (TreeNode*)malloc(sizeof(TreeNode));
right->val = nums[i+1];
right->left = right->right = NULL;
cur->right = right;
queue[rear++] = right;
}
}
free(queue);
return root;
}
int main() {
int nums[] = {1, 2, 3, 4, 5, -1, 6, -1, -1, 7};
int n = sizeof(nums) / sizeof(int);
TreeNode *root = createTree(nums, n);
return 0;
}
```
上述代码中,我们用一个数组`nums`来表示一棵二叉树。其中,-1表示该节点为空。我们通过队列来辅助构建二叉树,同时也可以用队列来实现二叉树的层次遍历等操作。