C语言用数组构建一颗二叉树,并分别完成前序遍历,中序遍历,后续遍历,层序遍历后输出遍历结果
时间: 2024-05-02 12:23:40 浏览: 103
对所建立的二叉树分别进行先序、中序和后序遍历,并输出结果。
4星 · 用户满意度95%
好的,我知道你要求了。关于你的问题,以下是C语言用数组构建一颗二叉树,并分别完成前序遍历,中序遍历,后序遍历,层序遍历后输出遍历结果的代码:
```
#include <stdio.h>
#define MAXSIZE 1024
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}BiTreeNode;
// 初始化二叉树结点
void Init_BiTree_Node(BiTreeNode* node, int data){
node -> data = data;
node -> left = NULL;
node -> right = NULL;
}
// 用数组构建一棵二叉树
void Create_BiTree(BiTreeNode* node, int arr[], int i, int len){
if (i > len){
return;
}
Init_BiTree_Node(node, arr[i - 1]);
if (2 * i <= len){
node -> left = (BiTreeNode*)malloc(sizeof(BiTreeNode));
Create_BiTree(node -> left, arr, 2 * i, len);
}
if (2 * i + 1 <= len){
node -> right = (BiTreeNode*)malloc(sizeof(BiTreeNode));
Create_BiTree(node -> right, arr, 2 * i + 1, len);
}
}
// 前序遍历
void PreOrderTraverse(BiTreeNode* node){
if (node != NULL){
printf("%d ", node -> data);
PreOrderTraverse(node -> left);
PreOrderTraverse(node -> right);
}
}
// 中序遍历
void InOrderTraverse(BiTreeNode* node){
if (node != NULL){
InOrderTraverse(node -> left);
printf("%d ", node -> data);
InOrderTraverse(node -> right);
}
}
// 后序遍历
void PostOrderTraverse(BiTreeNode* node){
if (node != NULL){
PostOrderTraverse(node -> left);
PostOrderTraverse(node -> right);
printf("%d ", node -> data);
}
}
// 层序遍历
void LevelOrderTraverse(BiTreeNode* root){
BiTreeNode* queue[MAXSIZE];
int front = 0, rear = 0;
if(root){
queue[rear++] = root;
}
while(front != rear){
BiTreeNode* p = queue[front++];
printf("%d ", p -> data);
if(p -> left){
queue[rear++] = p -> left;
}
if(p -> right){
queue[rear++] = p -> right;
}
}
}
int main(){
// 定义一个数组
int arr[7] = {1, 2, 3, 4, 5, 6, 7};
// 构建二叉树
BiTreeNode *root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
Create_BiTree(root, arr, 1, 7);
// 前序遍历并输出结果
printf("Pre-order traversal:\n");
PreOrderTraverse(root);
printf("\n");
// 中序遍历并输出结果
printf("In-order traversal:\n");
InOrderTraverse(root);
printf("\n");
// 后序遍历并输出结果
printf("Post-order traversal:\n");
PostOrderTraverse(root);
printf("\n");
// 层序遍历并输出结果
printf("Level-order traversal:\n");
LevelOrderTraverse(root);
return 0;
}
```
希望这段代码能够解决你的问题。
阅读全文