C语言非递归后序遍历二叉树
时间: 2023-11-03 12:07:52 浏览: 74
非递归后序遍历二叉树的方法是使用栈,从根节点开始遍历,每当遇到非叶子节点,将其入栈,递归遍历其左子树,再遍历其右子树。当遍历完右子树后,再从栈中弹出该节点并输出。
具体实现步骤如下:
1. 定义一个栈和一个指针,指向当前节点,初始时指向根节点。
2. 循环遍历,直到栈为空且当前节点为空。
3. 如果当前节点不为空,将其入栈,指针指向其左子树,继续循环。
4. 如果当前节点为空,从栈中弹出一个节点,指针指向该节点的右子树。
5. 如果该节点没有右子树或者右子树已经遍历完,则输出该节点的值。
6. 重复步骤 3~5,直到栈为空且当前节点为空。
下面是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Stack {
int top;
int size;
TreeNode **data;
} Stack;
Stack *createStack(int size) {
Stack *stack = (Stack*) malloc(sizeof(Stack));
stack->top = -1;
stack->size = size;
stack->data = (TreeNode**) malloc(size * sizeof(TreeNode*));
return stack;
}
int isStackEmpty(Stack *stack) {
return stack->top == -1;
}
void push(Stack *stack, TreeNode *node) {
if (stack->top == stack->size - 1) return;
stack->top++;
stack->data[stack->top] = node;
}
TreeNode *pop(Stack *stack) {
if (isStackEmpty(stack)) return NULL;
TreeNode *node = stack->data[stack->top];
stack->top--;
return node;
}
void destroyStack(Stack *stack) {
free(stack->data);
free(stack);
}
void postorderTraversal(TreeNode *root) {
if (root == NULL) return;
Stack *stack = createStack(100);
TreeNode *cur = root;
TreeNode *lastVisited = NULL;
while (!isStackEmpty(stack) || cur != NULL) {
if (cur != NULL) {
push(stack, cur);
cur = cur->left;
} else {
TreeNode *node = stack->data[stack->top];
if (node->right == NULL || node->right == lastVisited) {
printf("%d ", node->val);
lastVisited = node;
pop(stack);
} else {
cur = node->right;
}
}
}
destroyStack(stack);
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode*) malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*) malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*) malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*) malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*) malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 非递归后序遍历
postorderTraversal(root);
// 释放内存
free(root->left);
free(root->right->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```