利用C语言建立一个二叉树,实现二叉树前序遍历、中顺序
时间: 2023-12-01 13:03:21 浏览: 76
下面是利用C语言建立二叉树并实现前序遍历和中序遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 前序遍历函数
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data); // 先访问根节点
preorderTraversal(root->left); // 再遍历左子树
preorderTraversal(root->right); // 最后遍历右子树
}
// 中序遍历函数
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left); // 先遍历左子树
printf("%d ", root->data); // 再访问根节点
inorderTraversal(root->right); // 最后遍历右子树
}
// 创建二叉树函数
TreeNode* createTree() {
TreeNode* root = NULL;
int data;
scanf("%d", &data);
if (data != -1) {
root = (TreeNode*) malloc(sizeof(TreeNode));
root->data = data;
root->left = createTree();
root->right = createTree();
}
return root;
}
int main() {
TreeNode* root = createTree();
printf("前序遍历结果:");
preorderTraversal(root);
printf("\n");
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
return 0;
}
```
在这个示例中,我们首先定义了一个二叉树结构体,包括节点的值和左右子树的指针。然后,我们实现了前序遍历和中序遍历函数,其中前序遍历先访问根节点,然后遍历左右子树,中序遍历先遍历左子树,然后访问根节点,最后遍历右子树。
接下来,我们实现了一个创建二叉树的函数,它通过递归的方式不断读入输入的值,直到读入-1为止。如果读入的值不是-1,则创建一个新的节点,并递归调用左右子树的创建函数。
最后,我们在main函数中调用创建二叉树函数,并分别调用前序遍历和中序遍历函数,输出遍历结果。
注意事项:在实际使用中,需要注意内存泄漏问题,即在程序结束时需要释放二叉树占用的内存。
阅读全文