用C语言按照先序遍历的方式创建一个二叉链表; 然后 编程实现二叉树的先序、中序和后序算法; 再分别以先序、中序和后序的方式输出之前创建的二叉链表
时间: 2024-12-16 17:22:15 浏览: 5
二叉链表及建立既简单遍历
在C语言中,我们可以使用结构体表示节点,并通过指针将它们链接起来以构建二叉链表。以下是先序遍历创建二叉链表的基本步骤:
1. 定义节点结构体:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
2. 创建根节点并初始化二叉链表:
```c
TreeNode* createPreorderList(int arr[], int size) {
if (size == 0) return NULL;
TreeNode* root = malloc(sizeof(TreeNode));
root->val = arr[0];
if (size > 1) {
root->left = createPreorderList(arr + 1, size - 1);
root->right = createPreorderList(arr + size - 1, 0); // 如果数组中有剩余元素,右子树为空
}
return root;
}
```
这里的`arr[]`是一个整数数组,存储了二叉树的值。
接下来是二叉树的遍历算法实现(假设我们已经有了一个已构造好的二叉链表的头结点`root`):
1. 先序遍历(根-左-右):
```c
void preorderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->val); // 输出当前节点值
preorderTraversal(node->left); // 遍历左子树
preorderTraversal(node->right); // 遍历右子树
}
}
```
2. 中序遍历(左-根-右):
```c
void inorderTraversal(TreeNode* node) {
if (node != NULL) {
inorderTraversal(node->left); // 遍历左子树
printf("%d ", node->val); // 输出当前节点值
inorderTraversal(node->right); // 遍历右子树
}
}
```
3. 后序遍历(左-右-根):
```c
void postorderTraversal(TreeNode* node) {
if (node != NULL) {
postorderTraversal(node->left); // 遍历左子树
postorderTraversal(node->right); // 遍历右子树
printf("%d ", node->val); // 输出当前节点值
}
}
```
最后,调用这些函数就可以根据需要在控制台上看到以先序、中序或后序遍历的结果。
阅读全文