后序遍历非递归C语言代码
时间: 2024-06-13 22:01:37 浏览: 2
后序遍历是二叉树遍历的一种方式,它的遍历顺序是:先访问左子树,再访问右子树,最后访问根节点。下面是后序遍历的非递归C语言代码:
```
void PostorderTraversal(TreeNode* root)
{
if (root == NULL)
return;
TreeNode* stack[MAX_SIZE];
int top = -1;
TreeNode* lastVisit = NULL; // 上一次访问的节点
while (root != NULL || top != -1) {
while (root != NULL) { // 遍历左子树
stack[++top] = root;
root = root->left;
}
TreeNode* node = stack[top];
if (node->right == NULL || node->right == lastVisit) { // 右子树为空或已经遍历过
printf("%d ", node->val);
top--;
lastVisit = node;
} else { // 遍历右子树
root = node->right;
}
}
}
```
相关问题
后序遍历的非递归C语言代码
后序遍历的非递归 C 语言代码可以使用栈来实现。以下是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct Stack {
struct TreeNode* data[MAX_SIZE];
int top;
};
void push(struct Stack* stack, struct TreeNode* node) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack overflow\n");
return;
}
stack->top++;
stack->data[stack->top] = node;
}
struct TreeNode* pop(struct Stack* stack) {
if (stack->top == -1) {
printf("Stack underflow\n");
return NULL;
}
struct TreeNode* node = stack->data[stack->top];
stack->top--;
return node;
}
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct Stack* stack1 = (struct Stack*)malloc(sizeof(struct Stack));
struct Stack* stack2 = (struct Stack*)malloc(sizeof(struct Stack));
stack1->top = -1;
stack2->top = -1;
push(stack1, root);
while (stack1->top != -1) {
struct TreeNode* node = pop(stack1);
push(stack2, node);
if (node->left) {
push(stack1, node->left);
}
if (node->right) {
push(stack1, node->right);
}
}
while (stack2->top != -1) {
struct TreeNode* node = pop(stack2);
printf("%d ", node->val);
}
free(stack1);
free(stack2);
}
int main() {
// 构造示例二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node1->val = 2;
struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node2->val = 3;
root->left = node1;
root->right = node2;
node1->left = NULL;
node1->right = NULL;
node2->left = NULL;
node2->right = NULL;
printf("Postorder traversal: ");
postorderTraversal(root);
free(root);
free(node1);
free(node2);
return 0;
}
```
二叉树后序遍历非递归算法c语言
二叉树的后序遍历非递归算法可以使用栈来实现。具体步骤如下:
1. 定义一个栈和一个指针p,初始时p指向根节点,栈为空。
2. 循环执行以下操作,直到栈为空:
a. 将p指向的节点及其左子树依次入栈,直到p指向的节点没有左子树。
b. 循环执行以下操作,直到栈顶元素的右子树为空或者栈顶元素的右子树已经被访问过:
i. 将栈顶元素出栈,并将其右子树标记为已访问。
ii. 如果栈顶元素的右子树为空,或者栈顶元素的右子树已经被访问过,就输出栈顶元素。
c. 如果栈不为空,将栈顶元素的右子树标记为未访问,并将p指向栈顶元素的右子树。
具体的C语言代码如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void postorderTraversal(TreeNode* root) {
if (!root) {
return;
}
TreeNode* stack[100];
int top = -1;
TreeNode* p = root;
TreeNode* pre = NULL;
while (p || top != -1) {
while (p) {
stack[++top] = p;
p = p->left;
}
p = stack[top];
if (p->right == NULL || p->right == pre) {
printf("%d ", p->val);
pre = p;
top--;
p = NULL;
} else {
p = p->right;
}
}
}
```
其中,top表示栈顶指针,pre表示已经访问过的右子树的指针。具体实现中,我们使用一个数组来模拟栈,数组的大小可以根据实际情况进行修改。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)