用c语言实现:1. 建立自己的头文件BT.H,内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2. 建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。
时间: 2024-11-04 14:13:51 浏览: 72
在C语言中,为了实现二叉树的操作,我们首先需要在`BT.h`头文件中定义相关的数据结构以及重要的函数声明:
```c
// BT.h
#ifndef BT_H
#define BT_H
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建一个新的二叉树节点
TreeNode* createNode(int value);
// 二叉树的建立,这里采用递归的方式插入节点
TreeNode* buildTree(int arr[], int start, int end);
// 二叉树的遍历函数声明
void preOrder(TreeNode* root);
void inOrder(TreeNode* root);
void postOrder(TreeNode* root);
#endif // BT_H
```
接下来,我们在`BT.c`文件中实现上述函数:
```c
// BT.c
#include "BT.h"
// 创建新的节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!newNode) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// 二叉树构建函数
TreeNode* buildTree(int arr[], int start, int end) {
if (start > end)
return NULL;
int mid = (start + end) / 2;
TreeNode* root = createNode(arr[mid]);
root->left = buildTree(arr, start, mid - 1);
root->right = buildTree(arr, mid + 1, end);
return root;
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL)
return;
printf("%d ", root->data); // 输出节点值
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL)
return;
inOrder(root->left);
printf("%d ", root->data); // 输出节点值
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL)
return;
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data); // 输出节点值
}
```
最后,在`main.c`中测试这些函数:
```c
#include "BT.h"
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = buildTree(arr, 0, n - 1);
if (root == NULL) {
printf("Failed to build tree\n");
return 1;
}
printf("Preorder traversal: ");
preOrder(root);
printf("\n");
printf("Inorder traversal: ");
inOrder(root);
printf("\n");
printf("Postorder traversal: ");
postOrder(root);
printf("\n");
free(root);
return 0;
}
```
这个程序创建了一个二叉搜索树并实现了三种遍历方式。运行`main.c`将输出相应的遍历结果。
阅读全文