请用c语言代码帮我实现二叉树后序遍历的非递归算法,需要完整的代码,并且向我说明如何输入,并说明输出是什么
时间: 2024-03-24 07:39:23 浏览: 72
C语言数据结构之二叉树的非递归后序遍历算法
5星 · 资源好评率100%
好的,以下是二叉树后序遍历的非递归算法的完整C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct Stack {
int top;
TreeNode* arr[MAX_SIZE];
} Stack;
Stack* createStack() {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->top = -1;
return stack;
}
int isEmpty(Stack* stack) {
return stack->top == -1;
}
void push(Stack* stack, TreeNode* node) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow!\n");
return;
}
stack->arr[++stack->top] = node;
}
TreeNode* pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow!\n");
return NULL;
}
return stack->arr[stack->top--];
}
TreeNode* peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow!\n");
return NULL;
}
return stack->arr[stack->top];
}
void postOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
Stack* stack1 = createStack();
Stack* stack2 = createStack();
push(stack1, root);
while (!isEmpty(stack1)) {
TreeNode* node = pop(stack1);
push(stack2, node);
if (node->left != NULL) {
push(stack1, node->left);
}
if (node->right != NULL) {
push(stack1, node->right);
}
}
while (!isEmpty(stack2)) {
printf("%d ", pop(stack2)->data);
}
}
TreeNode* createTreeNode(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
// 创建二叉树
TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->left = createTreeNode(4);
root->left->right = createTreeNode(5);
root->right->left = createTreeNode(6);
root->right->right = createTreeNode(7);
// 后序遍历并输出结果
printf("后序遍历结果:");
postOrderTraversal(root);
printf("\n");
return 0;
}
```
在这段代码中,我们使用了两个栈来实现后序遍历。首先我们将根节点压入第一个栈中,然后将它弹出并压入第二个栈中。接着,我们依次将它的左右子树压入第一个栈中,重复以上步骤直到第一个栈为空。最后,我们从第二个栈中依次弹出节点并输出,即为后序遍历的结果。
在这段代码中,我们创建了一个二叉树,树的结构如下:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
程序输出的结果如下:
```
后序遍历结果:4 5 2 6 7 3 1
```
其中,`4 5 2 6 7 3 1` 就是这棵二叉树的后序遍历结果。
阅读全文