c语言手动输入序列创建二叉树t,采用顺序存储结构实现求二叉树的深度,并对二叉树进行先序遍历,中序遍历,后序遍历。 要求树中的数据类型约定为整型。并写出主函数
时间: 2024-11-06 21:14:10 浏览: 33
树子系统实现二叉树的创建,先序遍历,中序遍历,后序遍历,求叶子数,求结点数,求树的深度
在C语言中,手动输入序列创建二叉树并计算其深度、进行遍历通常需要以下几个步骤:
1. 定义节点结构体(Node),包含整型数据`data`和指向左右子节点的指针`left`和`right`。
```c
struct Node {
int data;
struct Node* left;
struct Node* right;
};
```
2. 创建一个递归函数来构建二叉搜索树(BST)从给定的有序序列。这里我们假设输入序列是升序排列的。
```c
struct Node* createBST(int arr[], int start, int end) {
if (start > end)
return NULL;
int mid = (start + end) / 2;
struct Node* root = (struct Node*)malloc(sizeof(struct Node));
root->data = arr[mid];
root->left = createBST(arr, start, mid - 1);
root->right = createBST(arr, mid + 1, end);
return root;
}
```
3. 计算二叉树的深度,可以使用递归或栈辅助的方式。这里给出递归版本:
```c
int maxDepth(struct Node* node) {
if (node == NULL)
return 0;
else
return 1 + MAX(maxDepth(node->left), maxDepth(node->right));
}
```
其中MAX是一个全局宏或者函数,返回两个数的最大值。
4. 实现先序、中序和后序遍历,同样使用递归。以下是遍历函数示例:
```c
void inorder(struct Node* node) {
if (node != NULL) {
inorder(node->left);
printf("%d ", node->data); // 中序遍历节点值
inorder(node->right);
}
}
void preorder(struct Node* node) {
if (node != NULL) {
printf("%d ", node->data); // 先序遍历节点值
preorder(node->left);
preorder(node->right);
}
}
void postorder(struct Node* node) {
if (node != NULL) {
preorder(node->left);
preorder(node->right);
printf("%d ", node->data); // 后序遍历节点值
}
}
```
5. 主函数(main),用于获取用户输入、创建二叉树、打印树的深度以及遍历:
```c
int main() {
int n, arr[100]; // 假设数组长度不超过100
printf("Enter the number of elements: ");
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &arr[i]);
}
struct Node* root = createBST(arr, 0, n - 1);
printf("Tree depth: %d\n", maxDepth(root));
printf("\nPreorder traversal: ");
preorder(root);
printf("\n");
printf("\nInorder traversal: ");
inorder(root);
printf("\n");
printf("\nPostorder traversal: ");
postorder(root);
printf("\n");
return 0;
}
```
在这个例子中,用户输入整数序列,程序会创建对应的二叉搜索树,然后计算深度并进行三种遍历。记得处理好内存分配和释放,避免内存泄漏。
阅读全文