请用C语言编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法
时间: 2024-05-14 20:17:33 浏览: 12
以下是C语言实现二叉树中序遍历和后续遍历的递归算法和非递归算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// 递归中序遍历
void inorderRecursive(Node* root) {
if (root == NULL) {
return;
}
inorderRecursive(root->left);
printf("%d ", root->data);
inorderRecursive(root->right);
}
// 递归后序遍历
void postorderRecursive(Node* root) {
if (root == NULL) {
return;
}
postorderRecursive(root->left);
postorderRecursive(root->right);
printf("%d ", root->data);
}
// 非递归中序遍历
void inorderIterative(Node* root) {
Node* stack[100];
int top = -1;
Node* current = root;
while (current != NULL || top != -1) {
while (current != NULL) {
stack[++top] = current;
current = current->left;
}
current = stack[top--];
printf("%d ", current->data);
current = current->right;
}
}
// 非递归后序遍历
void postorderIterative(Node* root) {
Node* stack1[100];
Node* stack2[100];
int top1 = -1;
int top2 = -1;
stack1[++top1] = root;
while (top1 != -1) {
Node* current = stack1[top1--];
stack2[++top2] = current;
if (current->left != NULL) {
stack1[++top1] = current->left;
}
if (current->right != NULL) {
stack1[++top1] = current->right;
}
}
while (top2 != -1) {
Node* current = stack2[top2--];
printf("%d ", current->data);
}
}
int main() {
Node* root = (Node*)malloc(sizeof(Node));
root->data = 1;
root->left = (Node*)malloc(sizeof(Node));
root->right = (Node*)malloc(sizeof(Node));
root->left->data = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right->data = 3;
root->right->left = (Node*)malloc(sizeof(Node));
root->right->right = NULL;
root->right->left->data = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
printf("递归中序遍历:\n");
inorderRecursive(root);
printf("\n");
printf("递归后序遍历:\n");
postorderRecursive(root);
printf("\n");
printf("非递归中序遍历:\n");
inorderIterative(root);
printf("\n");
printf("非递归后序遍历:\n");
postorderIterative(root);
printf("\n");
return 0;
}
```