试着写一个二叉树中序遍历的非递归算法。

好的，下面是二叉树中序遍历的非递归算法：

1. 初始化一个栈，并将根节点入栈。
2. 循环执行以下步骤直到栈为空：
- 弹出栈顶节点，并将其值输出。
- 如果该节点存在右子树，则将右子树入栈。
- 如果该节点存在左子树，则将左子树入栈。

代码实现如下（假设二叉树的节点定义为Node类）：

def inorder_traversal(root):
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        print(node.val)
        node = node.right

这个算法的时间复杂度是O(n)，其中n是二叉树节点的数量。

相关问题

用C语言实现二叉树中序遍历非递归算法

在C语言中，实现二叉树的非递归中序遍历通常需要借助栈数据结构。非递归的方法可以分为三个步骤：

1. 创建一个空栈，并将根节点压入栈中。
2. 当栈不为空时，执行循环：
a. 弹出栈顶元素，访问该元素（即当前节点）。
b. 如果当前节点有左子节点，将左子节点压入栈中。
c. 如果当前节点有右子节点，因为我们要按照"左-根-右"的顺序访问，跳过右子节点直接处理下一个节点（即检查下一个栈顶元素）。
3. 当栈为空且所有节点都已访问完，遍历结束。

以下是C语言的一个示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 非递归中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return; // 如果根节点为空，直接返回

    Stack<TreeNode*> stack; // 使用栈来辅助遍历
    TreeNode* curr = root; // 初始化当前节点

    while (curr != NULL || !stack.isEmpty()) { // 循环直到栈为空且当前节点也为空
        while (curr != NULL) {
            stack.push(curr); // 将当前节点压栈
            curr = curr->left; // 转向左子节点
        }

        curr = stack.pop(); // 弹出栈顶节点并访问
        printf("%d ", curr->val); // 打印节点值
        curr = curr->right; // 移动到右子节点
    }
}

int main() {
    // 示例二叉树
    TreeNode* root = malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->right = malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->left->left = malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    root->left->right = malloc(sizeof(TreeNode));
    root->left->right->val = 5;

    inorderTraversal(root);
    return 0;
}

运行此程序会打印出：`4 2 5 1 3`，这是二叉树 `1 - 2(4 5) - 3` 的中序遍历结果。

试着用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. 将当前结点更新为其右子树。

这样，可以保证所有结点都被访问且顺序正确，实现了二叉树的中序遍历。