不用递归,用栈实现二叉树的中序遍历、先序遍历、后续遍历C语言代码
时间: 2023-12-28 08:49:49 浏览: 69
C语言实现二叉树的中序遍历(非递归)
好的,以下是C语言代码实现二叉树的中序遍历、先序遍历、后续遍历,使用栈而非递归:
```C
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int size = 0;
while (root || size) {
while (root) {
stack[size++] = root;
root = root->left;
}
root = stack[--size];
printf("%d ", root->data);
root = root->right;
}
}
void preorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int size = 0;
while (root || size) {
while (root) {
printf("%d ", root->data);
stack[size++] = root;
root = root->left;
}
root = stack[--size];
root = root->right;
}
}
void postorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int size = 0;
struct TreeNode* lastVisited = root;
while (root || size) {
while (root) {
stack[size++] = root;
root = root->left;
}
root = stack[size - 1];
if (root->right && root->right != lastVisited) {
root = root->right;
} else {
printf("%d ", root->data);
lastVisited = root;
size--;
root = NULL;
}
}
}
int main() {
struct TreeNode a = {4, NULL, NULL};
struct TreeNode b = {5, NULL, NULL};
struct TreeNode c = {2, &a, &b};
struct TreeNode d = {6, NULL, NULL};
struct TreeNode e = {3, &d, NULL};
struct TreeNode f = {1, &c, &e};
inorderTraversal(&f);
printf("\n");
preorderTraversal(&f);
printf("\n");
postorderTraversal(&f);
printf("\n");
return 0;
}
```
请注意,这只是实现的一种方法,并不是唯一的正确答案。
阅读全文