C语言实现非递归后序遍历核心代码
时间: 2023-09-06 18:04:59 浏览: 71
### 回答1:
非递归后序遍历二叉树的核心代码如下:
```
void postorder_traverse(Node *root) {
if (root == NULL) return;
stack<Node*> s;
Node *curr = root;
Node *last_visited = NULL;
while (curr != NULL || !s.empty()) {
if (curr != NULL) {
s.push(curr);
curr = curr->left;
} else {
Node *peek_node = s.top();
// 如果右子树已经访问过了,则访问当前节点
if (peek_node->right != NULL && last_visited != peek_node->right) {
curr = peek_node->right;
} else {
printf("%d ", peek_node->val);
last_visited = peek_node;
s.pop();
}
}
}
}
```
这段代码使用了一个栈来帮助遍历二叉树。首先将根节点压入栈中,然后遍历左子树,如果左子树遍历完了就弹出栈顶元素并访问。如果右子树还没有被访问过,就将右子树的根节点压入栈中,继续遍历左子树。如果右子树已经被访问过了,就直接访问栈顶元素。
这段代码的时间复杂度为 O(n),空间复杂度为 O(n)。
希望这能帮到你!
### 回答2:
下面是C语言实现非递归后序遍历的核心代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 定义栈的结构体
struct Stack {
struct TreeNode* data[100];
int top;
};
// 初始化栈
void initStack(struct Stack* stack) {
stack->top = -1;
}
// 判断栈是否为空
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// 入栈
void push(struct Stack* stack, struct TreeNode* node) {
stack->data[++(stack->top)] = node;
}
// 出栈
struct TreeNode* pop(struct Stack* stack) {
return stack->data[(stack->top)--];
}
// 获取栈顶元素
struct TreeNode* top(struct Stack* stack) {
return stack->data[stack->top];
}
// 非递归后序遍历函数
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct Stack stack;
initStack(&stack);
struct TreeNode* previsited = NULL;
struct TreeNode* curr = root;
while (curr != NULL || !isEmpty(&stack)) {
while (curr != NULL) {
push(&stack,curr);
curr = curr->left;
}
curr = top(&stack);
if (curr->right == NULL || curr->right == previsited) {
printf("%d ",curr->val); // 输出节点的值
pop(&stack);
previsited = curr;
curr = NULL;
} else {
curr = curr->right;
}
}
}
int main() {
// 构建二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* node3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* node4 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = node1;
root->right = node2;
node1->val = 2;
node1->left = node3;
node1->right = NULL;
node2->val = 3;
node2->left = NULL;
node2->right = node4;
node3->val = 4;
node3->left = NULL;
node3->right = NULL;
node4->val = 5;
node4->left = NULL;
node4->right = NULL;
// 非递归后序遍历二叉树
postorderTraversal(root);
// 释放内存
free(root);
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
}
```
上述代码中定义了一个`TreeNode`结构体表示二叉树节点,以及一个`Stack`结构体表示栈。其中`initStack()`函数用于初始化栈,`isEmpty()`函数用于判断栈是否为空,`push()`函数用于入栈,`pop()`函数用于出栈,`top()`函数用于获取栈顶元素。
主函数中通过手动构建一个二叉树,并调用`postorderTraversal()`函数进行非递归后序遍历,最后释放所分配的内存。
### 回答3:
非递归后序遍历是指先遍历左子树,再遍历右子树,最后访问根节点。下面是C语言实现非递归后序遍历的核心代码:
```c
// 定义树的节点结构
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义栈的结构
typedef struct Stack {
TreeNode* data[STACK_SIZE]; // 假设栈的最大容量为STACK_SIZE
int top;
} Stack;
// 后序遍历函数
void postorderTraversal(TreeNode* root) {
Stack stack;
stack.top = -1; // 初始化栈为空
TreeNode* curr = root; // 当前节点指针
TreeNode* last = NULL; // 上一次访问的节点指针
while (curr != NULL || stack.top != -1) {
// 遍历到最左子节点并将路径上的节点入栈
while (curr != NULL) {
stack.data[++stack.top] = curr;
curr = curr->left;
}
// 当前节点没有右子节点或者上一次访问的节点为其右子节点时,访问当前节点
curr = stack.data[stack.top];
if (curr->right == NULL || curr->right == last) {
printf("%d ", curr->data);
stack.top--;
last = curr;
curr = NULL;
}
else {
curr = curr->right;
}
}
}
```
在这段代码中,使用了一个栈来帮助实现非递归后序遍历。首先遍历到最左子节点并将路径上的节点入栈,然后判断当前节点是否有右子节点。如果没有右子节点或者上一次访问的节点是其右子节点时,访问当前节点,并将其出栈,然后将上一次访问的节点设为当前节点,将当前节点指针置空。否则,将当前节点指针指向其右子节点。重复以上步骤,直到栈为空。最后就完成了非递归后序遍历。