建立二叉树,然后用c语言实现:输出先序遍历、中序遍历、后序遍历的结果。输入说明:第一行:结点个数n。以下行:每行三个数,第一个是父亲,后两个依次为左右孩子,0表示空。输出说明:根、先中后序遍历结果。
时间: 2024-10-29 08:19:47 浏览: 109
建立二叉树并实现其先序、中序和后序遍历可以分为以下几个步骤:
1. 定义二叉树节点结构体:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
2. 创建函数来插入节点并构建二叉树:
```c
TreeNode* insertNode(TreeNode* root, int val) {
if (root == NULL) {
return (TreeNode*)malloc(sizeof(TreeNode));
}
if (val < root->val) {
root->left = insertNode(root->left, val);
} else {
root->right = insertNode(root->right, val);
}
return root;
}
```
3. 实现先序遍历(根-左-右):
```c
void preorderTraversal(TreeNode* root, char* output) {
if (root != NULL) {
output[0] = root->val + '0';
output++;
preorderTraversal(root->left, output);
preorderTraversal(root->right, output);
}
}
```
4. 中序遍历(左-根-右):
```c
void inorderTraversal(TreeNode* root, char* output) {
if (root != NULL) {
inorderTraversal(root->left, output);
output[0] = root->val + '0';
output++;
inorderTraversal(root->right, output);
}
}
```
5. 后序遍历(左-右-根):
```c
void postorderTraversal(TreeNode* root, char* output) {
if (root != NULL) {
postorderTraversal(root->left, output);
postorderTraversal(root->right, output);
output[0] = root->val + '0';
output++;
}
}
```
6. 主函数,读取输入,创建二叉树,并打印遍历结果:
```c
int main() {
int n;
scanf("%d", &n);
TreeNode* root = NULL;
char result[1000];
for (int i = 0; i < n; i++) {
int parent, left, right;
scanf("%d %d %d", &parent, &left, &right);
root = insertNode(root, left ? left : 0);
// ... (同样的处理右子节点)
}
preorderTraversal(root, result);
printf("Preorder: ");
for (char* p = result; *p != '\0'; p++)
printf("%d ", *p - '0');
printf("\n");
inorderTraversal(root, result);
printf("Inorder: ");
for (char* p = result; *p != '\0'; p++)
printf("%d ", *p - '0');
printf("\n");
postorderTraversal(root, result);
printf("Postorder: ");
for (char* p = result; *p != '\0'; p++)
printf("%d ", *p - '0');
printf("\n");
return 0;
}
```
以上代码只是一个基础示例,实际应用中可能需要考虑内存管理和其他错误处理。
阅读全文