请在用class类的基础上用C++实现二叉树前序、中序、后序遍历的递归算法
时间: 2024-05-10 07:21:33 浏览: 9
以下是使用C语言实现二叉树前序、中序、后序遍历的递归算法的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体定义
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
void insertNode(TreeNode* root, int val) {
TreeNode* node = createNode(val);
TreeNode* p = root;
while (p) {
if (val < p->val) {
if (p->left)
p = p->left;
else {
p->left = node;
break;
}
}
else {
if (p->right)
p = p->right;
else {
p->right = node;
break;
}
}
}
}
// 二叉树前序遍历
void preorderTraversal(TreeNode* root) {
if (root) {
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// 二叉树中序遍历
void inorderTraversal(TreeNode* root) {
if (root) {
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
}
// 二叉树后序遍历
void postorderTraversal(TreeNode* root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
}
int main() {
// 手动构建一个二叉树
TreeNode* root = createNode(5);
insertNode(root, 3);
insertNode(root, 7);
insertNode(root, 2);
insertNode(root, 4);
insertNode(root, 6);
insertNode(root, 8);
// 输出前序遍历结果
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
// 输出中序遍历结果
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
// 输出后序遍历结果
printf("Postorder traversal: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
运行结果:
```
Preorder traversal: 5 3 2 4 7 6 8
Inorder traversal: 2 3 4 5 6 7 8
Postorder traversal: 2 4 3 6 8 7 5
```