C语言建立一棵二叉树,编程实现二叉树的如下基本操作: 按先序序列构造一棵二叉链表表示的二叉树T; 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 求二叉树的深度结点数目叶结点数目,将二叉树每个结点的左右子数交换位置
时间: 2024-12-17 14:13:07 浏览: 12
在C语言中,我们首先需要定义一个二叉树节点结构体,包含数据域和指向左右孩子的指针。然后可以按照递归的方式实现以下几个基本操作:
1. **构造先序二叉链表**:
- 定义节点结构体 `typedef struct TreeNode`:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
- 先序遍历(根-左-右)的构建函数:
```c
void buildPreorder(TreeNode** root, int arr[], int start, int end) {
if (start > end) return;
TreeNode* node = malloc(sizeof(TreeNode));
node->val = arr[start];
node->left = NULL;
node->right = NULL;
// 递归插入左子树和右子树
buildPreorder(&node->left, arr, start + 1, end);
buildPreorder(&node->right, arr, start + 1, end);
*root = node; // 更新根节点
}
```
2. **遍历二叉树**:
- 先序遍历: 调用 `inOrderTraversal(root)`
- 中序遍历: 调用 `inOrderTraversal(root)`
- 后序遍历: 调用 `postOrderTraversal(root)`
- 层次遍历(广度优先搜索): 使用队列实现,参考下面的代码片段
3. **计算深度、结点数和叶结点数**:
- 深度: 函数 `int maxDepth(TreeNode* root)`
- 结点数: 函数 `int totalNodes(TreeNode* root)`
- 叶子节点数: 函数 `int leafCount(TreeNode* root)`
4. **交换子节点**:
- 函数 `swapChildren(TreeNode* node)` 或者 `switchSubtrees(TreeNode* root)` 来交换每个节点的左右子节点。
由于篇幅原因,这里只给出了关键部分的代码框架,完整的代码实现会更长。如果你需要具体的代码示例,我可以为你提供。不过请注意,在实际编写过程中,你需要处理一些边界情况,如空树和只有一个元素的树等。
阅读全文