层序次序创建二叉树,用C语言实现,只需要代码
时间: 2023-09-19 19:06:39 浏览: 91
数据结构层序中序遍历构建二叉树
### 回答1:
层序次序创建二叉树指的是通过输入每个节点的值来创建一棵二叉树,这种方式按照节点在二叉树中的层次顺序(从上到下,从左到右)进行输入。
下面是用 C 语言实现层序次序创建二叉树的代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建一个新的节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 层序次序创建二叉树
TreeNode* createBinaryTreeByLevelOrder() {
int val;
TreeNode* root = NULL;
TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*)); // 用来保存每一层的节点
int size = 0; // nodes 数组中保存的节点个数
int front = 0; // nodes 数组中第一个需要处理的节点的索引
int rear = 0; // nodes 数组中最后一个节点的后一个位置的索引
// 循环读入节点的值
while (scanf("%d", &val) != EOF) {
// 创建一个新的节点
TreeNode* node = createNode(val);
// 将节点加入到 nodes 数组中
nodes[rear++] = node;
size++;
// 处理当前节点的左右子节点
if (root == NULL) {
// 如果是第一个节点,则将它作为根节点
root = node;
} else {
//
### 回答2:
以下是使用C语言实现层序次序创建二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 创建新节点
struct TreeNode* createNode(int value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 层序创建二叉树
struct TreeNode* createBinaryTree(int values[], int size) {
if (size == 0) {
return NULL;
}
struct TreeNode* root = createNode(values[0]);
struct TreeNode* nodes[size];
nodes[0] = root;
int i, parentIndex;
for (i = 1; i < size; i++) {
parentIndex = (i - 1) / 2;
struct TreeNode* parentNode = nodes[parentIndex];
struct TreeNode* currentNode = createNode(values[i]);
if (i % 2 != 0) {
parentNode->left = currentNode;
} else {
parentNode->right = currentNode;
}
nodes[i] = currentNode;
}
return root;
}
// 打印二叉树(前序遍历)
void printBinaryTree(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
printBinaryTree(root->left);
printBinaryTree(root->right);
}
int main() {
int values[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(values) / sizeof(values[0]);
struct TreeNode* root = createBinaryTree(values, size);
printf("层序创建的二叉树:\n");
printBinaryTree(root);
printf("\n");
return 0;
}
```
这段代码通过一个整型数组 `values` 作为节点数据,按照层序次序构建二叉树,并通过前序遍历打印二叉树的结果。
### 回答3:
下面是使用C语言实现层序创建二叉树的代码:
```c
#include<stdio.h>
#include<stdlib.h>
/* 二叉树结点 */
typedef struct TreeNode {
int data; // 结点数据
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
} TreeNode;
/* 层序创建二叉树 */
TreeNode* createBinaryTree(int arr[], int size) {
if (size <= 0) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); // 创建根结点
root->data = arr[0];
root->left = NULL;
root->right = NULL;
TreeNode* queue[size]; // 创建队列用于层序遍历
int front = 0, rear = 0; // 队列头尾指针
queue[rear++] = root; // 根结点入队列
int i;
for (i = 1; i < size; i++) {
TreeNode* parent = queue[front]; // 当前结点的父结点
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); // 创建新结点
newNode->data = arr[i];
newNode->left = NULL;
newNode->right = NULL;
if (parent->left == NULL) {
parent->left = newNode; // 左子树为空,新结点为左子结点
}
else if (parent->right == NULL) {
parent->right = newNode; // 右子树为空,新结点为右子结点
front++; // 父结点已有左右子结点,父结点出队列
}
queue[rear++] = newNode; // 新结点入队列
}
return root;
}
/* 测试 */
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = createBinaryTree(arr, size);
// 输出层序遍历结果
TreeNode* queue[size];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
printf("%d ", node->data);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
return 0;
}
```
上述代码实现了层序创建二叉树的功能。首先定义了一个`TreeNode`结构体作为二叉树结点,每个结点包含了数据以及左右子树指针。然后使用`createBinaryTree`函数来进行层序创建二叉树的操作,该函数接受一个整型数组和数组大小作为参数,返回创建好的二叉树的根结点。函数内部使用循环遍历数组,创建结点并根据层序顺序连接结点之间的关系。最后,将创建好的二叉树按层序遍历的顺序输出,验证二叉树的创建是否正确。
阅读全文