1、运行时从键盘输入先序序列,创建对应二叉树,再分别对其进行前、中、后序遍历,输出每个遍历序列。分别使用c语言和c++代码
时间: 2024-10-18 14:16:44 浏览: 31
为了演示如何在C语言和C++中完成这个任务,我会给出基本的算法和代码示例。首先,我们需要一个函数来将先序遍历序列转换为二叉树:
```c
#include <stdio.h>
// C语言中二叉树节点的定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 函数用于构建二叉树
TreeNode* buildTree(int* preorder, int n) {
if (n == 0) return NULL;
TreeNode* root = &preorder[0];
TreeNode* left = buildTree(&preorder[1], n / 2);
TreeNode* right = buildTree(&preorder[n / 2 + 1], n - n / 2 - 1);
root->left = left;
root->right = right;
return root;
}
// C++版本的构建二叉树函数
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTreeCPP(vector<int>& preorder) {
// ... 类似C语言版本,只是更倾向于模板和智能指针
}
```
接下来,我们分别实现前、中、后序遍历并输出结果:
```c
// C语言版本的遍历函数
void printPreOrder(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val); // 先序遍历
printPreOrder(root->left);
printPreOrder(root->right);
}
}
// 中序遍历和后续遍历类似,只需调整递归顺序
void printInOrder(TreeNode* root) { ... }
void printPostOrder(TreeNode* root) { ... }
int main() {
int preorder[] = {1, 2, 3, 4, 5};
int n = sizeof(preorder) / sizeof(preorder[0]);
TreeNode* root = buildTree(preorder, n);
printf("先序遍历: ");
printPreOrder(root);
printf("\n");
// ... 同样为中序和后序遍历添加相应代码
return 0;
}
// C++版本的主函数
int main() {
vector<int> preorder = {1, 2, 3, 4, 5};
TreeNode* root = buildTreeCPP(preorder);
// ... 使用智能指针替换裸指针,并添加相应遍历函数
return 0;
}
```
以上代码仅为基本示例,实际编程时需要考虑错误处理和边界情况。在C++中,可以使用`std::vector`代替数组,并利用现代C++的特性优化代码。
阅读全文