用c语言编写1.定义二叉链存储结构。 2.建立二叉链表存储的二叉树。 3.实现二叉树的先序遍历、中序遍历和后序遍历。 4.实现求二叉树的高度、求结点双亲、统计叶子结点数目的操作。 5.编写测试主函数,测试所实现的操作,并进行分析。详细过程
时间: 2024-12-08 14:21:21 浏览: 29
在 C 语言中,我们首先需要定义二叉链表的数据结构,通常会包括节点结构体,包含数据域(通常是 int 或者 void*),以及左右指针:
```c
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
接下来,我们可以创建二叉树并插入节点,例如通过递归的方式:
```c
TreeNode* createBinaryTree(int arr[], int n) {
if (n <= 0)
return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = arr[0];
int i = 1;
if (2 * n > 1) {
root->left = createBinaryTree(arr, n / 2);
root->right = createBinaryTree(arr + n / 2, n - n / 2);
}
return root;
}
```
遍历二叉树有三种基本方法:
1. 先序遍历(根-左-右):
```c
void preOrderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->data);
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
}
```
2. 中序遍历(左-根-右):
```c
void inOrderTraversal(TreeNode* node) {
if (node != NULL) {
inOrderTraversal(node->left);
printf("%d ", node->data);
inOrderTraversal(node->right);
}
}
```
3. 后序遍历(左-右-根):
```c
void postOrderTraversal(TreeNode* node) {
if (node != NULL) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->data);
}
}
```
其他操作如计算高度、寻找父节点和计数叶节点可以这样实现:
1. 高度:
```c
int height(TreeNode* node) {
if (node == NULL)
return 0;
else
return 1 + MAX(height(node->left), height(node->right));
}
// MAX 函数用于返回两个整数的最大值
int max(int a, int b) { return a > b ? a : b; }
```
2. 双亲查找:
这取决于具体的存储结构,如果每个节点都保存其父节点指针,那么直接访问即可。
3. 计算叶节点数:
```c
int countLeaves(TreeNode* node) {
if (node == NULL)
return 0;
else if (node->left == NULL && node->right == NULL)
return 1;
else
return countLeaves(node->left) + countLeaves(node->right);
}
```
最后,在 main 函数中,你可以创建一个数组,构建二叉树,然后分别调用上述函数进行测试。记得处理好内存分配和释放,避免内存泄漏。这里只是一个概要,实际代码可能还需要处理边界条件和其他细节。
阅读全文