使用C++掌握二叉树的初始化、建立、打印输出二叉树,先序、中序、后序遍历二叉树的递归实现等基本操作,实现二叉树的层次遍历
时间: 2023-12-01 09:03:12 浏览: 107
以下是使用 C 语言实现二叉树的初始化、建立、打印输出二叉树,先序、中序、后序遍历二叉树的递归实现,以及二叉树的层次遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树的结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 初始化二叉树
TreeNode* initTree() {
return NULL;
}
// 递归建立二叉树
TreeNode* createTree() {
TreeNode* root = NULL;
int value;
scanf("%d", &value);
if (value != -1) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = value;
root->left = createTree();
root->right = createTree();
}
return root;
}
// 先序遍历二叉树
void preOrder(TreeNode* root) {
if (root) {
printf("%d ", root->val);
preOrder(root->left);
preOrder(root->right);
}
}
// 中序遍历二叉树
void inOrder(TreeNode* root) {
if (root) {
inOrder(root->left);
printf("%d ", root->val);
inOrder(root->right);
}
}
// 后序遍历二叉树
void postOrder(TreeNode* root) {
if (root) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->val);
}
}
// 层次遍历二叉树,借助队列实现
void levelOrder(TreeNode* root) {
if (!root) return;
TreeNode* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
TreeNode* node = queue[front++];
printf("%d ", node->val);
if (node->left) queue[rear++] = node->left;
if (node->right) queue[rear++] = node->right;
}
}
int main() {
TreeNode* root = initTree();
printf("请输入二叉树的结点,-1表示空结点:\n");
root = createTree();
printf("先序遍历结果:");
preOrder(root);
printf("\n中序遍历结果:");
inOrder(root);
printf("\n后序遍历结果:");
postOrder(root);
printf("\n层次遍历结果:");
levelOrder(root);
printf("\n");
return 0;
}
```
在上述代码中,我们定义了一个二叉树的结构体 `TreeNode`,包含了结点的值 `val`,以及左子树和右子树的指针 `left` 和 `right`。我们通过 `createTree()` 函数递归地建立二叉树,并通过 `preOrder()`、`inOrder()`、`postOrder()` 函数分别实现了先序、中序、后序遍历二叉树的递归操作。最后,我们通过 `levelOrder()` 函数实现了层次遍历二叉树的操作,使用队列来辅助实现。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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://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)