试着写一个二叉树中序遍历的非递归算法。
时间: 2023-06-16 11:06:00 浏览: 68
二叉树的中序遍历非递归算法可以用栈来实现,具体步骤如下:
1. 初始化栈,将根节点压入栈中。
2. 当栈不为空时,循环执行下列操作:
1)将栈顶元素弹出并输出。
2)如果该节点有右子树,则将右子树压入栈中。
3)如果该节点有左子树,则将左子树压入栈中。
下面是使用 Python 语言实现的代码:
```python
def inorderTraversal(root):
result = []
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
result.append(node.val)
node = node.right
return result
```
在这个代码中,我们定义了一个列表 result 和一个栈 stack,然后初始化根节点 node 为二叉树的根节点。
在 while 循环中,我们首先将所有左子树节点压入栈中,然后将栈顶节点弹出并输出,接着将右子树节点压入栈中。由于栈的后进先出特性,这样可以保证输出的顺序为中序遍历的顺序。
当遍历完所有节点后,返回 result 列表即可。
相关问题
试着用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语言实现二叉树中序遍历的非递归算法的核心代码:
```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。
通过这样的遍历方式,可以保证左子树的节点都在右子树之前被访问,从而实现了中序遍历的效果。
阅读全文