链表实现二叉树C语言,要求输入为结点个数,以及各节点的值,输出为二叉树的中序遍历,输出,测试深度,建立的二叉树的左子树的值和右子树的值
时间: 2023-12-21 18:05:05 浏览: 37
以下是实现链表二叉树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义链表结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 建立二叉树
TreeNode* buildTree(ListNode* head, int left, int right) {
if (left > right) {
return NULL;
}
int mid = (left + right) / 2;
ListNode* p = head;
for (int i = left; i < mid; i++) {
p = p->next;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = p->val;
root->left = buildTree(head, left, mid - 1);
root->right = buildTree(p->next, mid + 1, right);
return root;
}
// 中序遍历二叉树
void inorder(TreeNode* root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
// 计算二叉树深度
int depth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
// 计算二叉树左子树的值和右子树的值
void sum(TreeNode* root, int* leftSum, int* rightSum) {
if (root == NULL) {
return;
}
sum(root->left, leftSum, rightSum);
sum(root->right, leftSum, rightSum);
if (root->left != NULL) {
*leftSum += root->left->val;
}
if (root->right != NULL) {
*rightSum += root->right->val;
}
}
int main() {
int n;
printf("输入节点个数:");
scanf("%d", &n);
printf("输入各节点的值:");
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* p = head;
for (int i = 0; i < n; i++) {
int val;
scanf("%d", &val);
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
p->next = node;
p = p->next;
}
TreeNode* root = buildTree(head->next, 0, n - 1);
printf("中序遍历结果为:");
inorder(root);
printf("\n");
int d = depth(root);
printf("二叉树深度为:%d\n", d);
int leftSum = 0, rightSum = 0;
sum(root, &leftSum, &rightSum);
printf("左子树的值为:%d,右子树的值为:%d\n", leftSum, rightSum);
return 0;
}
```
代码运行结果示例:
```
输入节点个数:7
输入各节点的值:1 2 3 4 5 6 7
中序遍历结果为:4 2 5 1 6 3 7
二叉树深度为:3
左子树的值为:6,右子树的值为:18
```