用C语言实现二叉树的基本操作: (1)实现二叉树的创建功能; (2)实现遍历功能,先序;打印出遍历序列; (3)实现“结点的度”的统计功能;输出每个结点的度;(4)计算树的深度。
时间: 2023-11-28 22:49:37 浏览: 89
下面是用C语言实现二叉树基本操作的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* createBinaryTree() {
int value;
scanf("%d", &value);
if (value == -1) {
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->data = value;
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
void preorderTraversal(struct TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
int countDegree(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int degree = 0;
if (root->left != NULL) {
degree++;
}
if (root->right != NULL) {
degree++;
}
return degree;
}
void printDegree(struct TreeNode* root) {
if (root != NULL) {
printf("Node %d has degree %d\n", root->data, countDegree(root));
printDegree(root->left);
printDegree(root->right);
}
}
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
int main() {
struct TreeNode* root = createBinaryTree();
printf("Preorder Traversal: ");
preorderTraversal(root);
printf("\n");
printf("Node Degree:\n");
printDegree(root);
printf("Tree Depth: %d\n", maxDepth(root));
return 0;
}
```
在上面的代码中,我们定义了一个二叉树结构体`struct TreeNode`,包含了每个节点的数据`data`以及左右子树指针`left`和`right`。然后我们实现了二叉树的创建函数`createBinaryTree`,遍历函数`preorderTraversal`,计算节点度数函数`countDegree`,打印节点度数函数`printDegree`,以及计算树深度函数`maxDepth`。
在`createBinaryTree`函数中,用户输入二叉树的节点值,如果输入-1则表示该节点为空,否则创建一个新节点,并递归创建它的左右子树。在`preorderTraversal`函数中,先打印当前节点的值,再递归遍历左右子树。在`countDegree`函数中,计算当前节点的度数,即有几个子节点。在`printDegree`函数中,递归打印每个节点的度数。在`maxDepth`函数中,递归计算每个节点的深度,并返回最大深度。
最后,在`main`函数中,我们调用上述函数,并输出遍历序列、节点度数和树的深度。
阅读全文