试着用C语言写一个二叉树中序遍历的非递归算法的核心代码。
时间: 2024-05-10 21:16:24 浏览: 10
以下是用C语言实现二叉树中序遍历的非递归算法的核心代码:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[1000];
int top = -1;
struct TreeNode* node = root;
while (node != NULL || top >= 0) {
while (node != NULL) {
stack[++top] = node;
node = node->left;
}
node = stack[top--];
printf("%d ", node->val);
node = node->right;
}
}
```
该算法的核心思想是使用栈来模拟递归的过程,具体实现方式为:
1. 从根节点开始,一直将左子节点压入栈中,直到遇到叶子节点为止。
2. 弹出栈顶元素并访问它。
3. 将当前节点指向右子节点,回到步骤1。
通过这样的遍历方式,可以保证左子树的节点都在右子树之前被访问,从而实现了中序遍历的效果。
相关问题
试着用C语言写一个二叉树中序遍历的非递归算法。
好的,下面是一个二叉树中序遍历的非递归算法的C语言实现:
```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 capacity;
TreeNode** data;
} Stack;
/* 初始化栈 */
Stack* initStack(int capacity) {
Stack* stack = (Stack*) malloc(sizeof(Stack));
stack->top = -1;
stack->capacity = capacity;
stack->data = (TreeNode**) malloc(sizeof(TreeNode*) * capacity);
return stack;
}
/* 判断栈是否为空 */
int isEmpty(Stack* stack) {
return stack->top == -1;
}
/* 判断栈是否已满 */
int isFull(Stack* stack) {
return stack->top == stack->capacity - 1;
}
/* 入栈 */
void push(Stack* stack, TreeNode* node) {
if (isFull(stack)) {
printf("Stack is full.\n");
return;
}
stack->data[++stack->top] = node;
}
/* 出栈 */
TreeNode* pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return NULL;
}
return stack->data[stack->top--];
}
/* 二叉树中序遍历的非递归算法 */
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
Stack* stack = initStack(100); // 初始化栈
TreeNode* node = root;
while (node != NULL || !isEmpty(stack)) {
while (node != NULL) { // 找到最左边的结点,并将路径上所有结点入栈
push(stack, node);
node = node->left;
}
node = pop(stack); // 出栈并访问
printf("%d ", node->val);
node = node->right; // 进入右子树
}
printf("\n");
}
/* 测试 */
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;
// 中序遍历
inorderTraversal(root);
return 0;
}
```
该算法使用了栈来辅助实现非递归遍历,具体过程如下:
1. 如果当前结点不为空,将其压入栈中,并将当前结点更新为其左子树。
2. 如果当前结点为空,说明已经到达最左边的结点,需要出栈并访问该结点。
3. 将当前结点更新为其右子树。
这样,可以保证所有结点都被访问且顺序正确,实现了二叉树的中序遍历。
试着用C语言写一个二叉树后序遍历的非递归算法的核心代码。
二叉树后序遍历的非递归算法可以使用栈来实现,具体实现如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
TreeNode* stack[1000];
int top = -1;
TreeNode* last = NULL;
while (root != NULL || top != -1) {
if (root != NULL) {
stack[++top] = root;
root = root->left;
} else {
TreeNode* tmp = stack[top];
if (tmp->right != NULL && tmp->right != last) {
root = tmp->right;
} else {
printf("%d ", tmp->val);
last = tmp;
top--;
}
}
}
}
```
其中,使用一个栈来保存节点,top表示栈顶元素的下标,last表示上一个被访问的节点。首先将根节点入栈,然后依次将其左子节点入栈。当左子节点为空时,弹出栈顶元素,如果该元素的右子节点不为空且没有被访问过,则将其右子节点入栈。如果右子节点为空或者已经被访问过,则访问该节点并将其标记为已访问,继续弹出栈顶元素。最终,栈为空时遍历结束。