如何用C语言分别实现先序遍历、中序遍历、后序遍历和层次遍历(广度优先遍历)二叉树?
时间: 2024-12-23 19:15:48 浏览: 4
在C语言中,我们可以使用结构体来表示二叉树节点,并通过递归或队列数据结构来实现四种遍历。以下是各自遍历的简单示例:
### 先序遍历 (Preorder)
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val); // 访问根节点
preorderTraversal(root->left); // 递归左子树
preorderTraversal(root->right); // 递归右子树
}
}
```
### 中序遍历 (Inorder)
```c
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left); // 递归左子树
printf("%d ", root->val); // 访问根节点
inorderTraversal(root->right); // 递归右子树
}
}
```
### 后序遍历 (Postorder)
```c
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left); // 递归左子树
postorderTraversal(root->right); // 递归右子树
printf("%d ", root->val); // 访问根节点
}
}
```
### 广度优先遍历 (Level Order Traversal / BFS)
```c
// 使用队列
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.enqueue(root);
while (!q.isEmpty()) {
TreeNode* node = q.dequeue();
printf("%d ", node->val);
if (node->left) q.enqueue(node->left);
if (node->right) q.enqueue(node->right);
}
}
```
上述代码都是基于递归实现的,如果需要迭代版本,你可以考虑将递归替换为栈或者使用循环和指针操作。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)