c语言手动输入序列创建二叉树t,采用顺序存储结构实现求二叉树的深度,并对二叉树进行先序遍历,中序遍历,后序遍历。 要求树中的数据类型约定为整型。
时间: 2024-11-07 15:13:05 浏览: 7
树子系统实现二叉树的创建,先序遍历,中序遍历,后序遍历,求叶子数,求结点数,求树的深度
在C语言中,我们可以手动输入序列创建二叉搜索树(BST),然后通过顺序存储结构计算其深度。首先,我们需要定义一个二叉树节点结构,包含整型数据和指向左右孩子的指针:
```c
typedef struct TreeNode {
int val; // 整数值
struct TreeNode *left; // 左孩子指针
struct TreeNode *right; // 右孩子指针
} TreeNode;
```
接下来,我们编写函数用于构建二叉树、计算深度以及遍历:
1. **创建二叉树**:
- 使用递归的方式从输入序列中构建二叉树,左孩子较小,右孩子较大。
```c
TreeNode* buildTree(int arr[], int start, int end) {
if (start > end)
return NULL;
int mid = (start + end) / 2;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = arr[mid];
root->left = buildTree(arr, start, mid - 1);
root->right = buildTree(arr, mid + 1, end);
return root;
}
```
2. **计算二叉树深度**:
- 使用递归或层次遍历来计算最大层级。
```c
int maxDepth(TreeNode* root) {
if (root == NULL)
return 0;
else {
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
}
```
3. **遍历二叉树**:
- 先序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根)。
```c
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val); // 打印当前节点值
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->val); // 打印当前节点值
inOrderTraversal(root->right);
}
}
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->val); // 打印当前节点值
}
}
```
阅读全文