生成一段将数组转化为平衡二叉树的C语言代码,并解释原理
时间: 2023-03-13 13:00:20 浏览: 86
C语言代码:
/* 将一个数组转化为平衡二叉树 */
struct node
{
int data;
struct node *left;
struct node *right;
};
/* 将数组转化为平衡二叉树 */
struct node* sortedArrayToBST(int arr[], int start, int end)
{
/* 如果start > end,返回空指针 */
if (start > end)
return NULL;
/* 找出中间点,建立根节点 */
int mid = (start + end)/2;
struct node *root = newNode(arr[mid]);
/* 使用中间点的左右子树来递归构建左右子树 */
root->left = sortedArrayToBST(arr, start, mid-1);
root->right = sortedArrayToBST(arr, mid+1, end);
return root;
} 原理:将一个有序数组转化为平衡二叉树的基本思想是,以数组的中间位置的值为根节点,将数组分成两半,分别对左右两部分分别构建左右子树,然后继续按同样的方式递归构建子树直至数组为空。
相关问题
生成一段递归生成二叉树的C语言代码
以下是一段递归生成二叉树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
struct Node* insert(struct Node* node, int data) {
if (node == NULL) {
return newNode(data);
}
if (data <= node->data) {
node->left = insert(node->left, data);
} else {
node->right = insert(node->right, data);
}
return node;
}
void inorderTraversal(struct Node* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
int main() {
struct Node* root = NULL;
int arr[] = { 5, 3, 7, 1, 9, 4, 2, 6, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
root = insert(root, arr[i]);
}
inorderTraversal(root);
return 0;
}
```
在上面的代码中,我们定义了一个二叉树的节点结构体 `Node`,其中包含了节点的数据、左子树和右子树。我们使用 `newNode()` 函数创建一个新的节点,使用 `insert()` 函数插入一个新的数据到二叉树中,使用 `inorderTraversal()` 函数对二叉树进行中序遍历输出。
在 `main()` 函数中,我们定义了一个数组 `arr`,然后使用 `for` 循环将数组中的元素逐个插入到二叉树中。最后输出二叉树的中序遍历结果。
生成一段C语言二叉树生成代码
好的,以下是一段简单的 C 语言代码,用于生成二叉树:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node* root = NULL;
int n, data;
printf("Enter the number of nodes in the binary tree: ");
scanf("%d", &n);
printf("Enter the data for the nodes:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &data);
root = insert(root, data);
}
printf("Inorder traversal of the binary tree: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
这个程序包含了二叉树节点的定义,创建节点和插入节点的函数,以及中序遍历二叉树的函数。在主函数中,用户可以输入二叉树的节点数和节点的数据,程序会自动创建二叉树并输出中序遍历结果。