二叉树的非递归中序遍历

二叉树的非递归中序遍历可以通过使用栈来实现。具体实现思路如下：

1. 从根节点开始，将所有左子树节点依次入栈，直到最左边的叶子节点。
2. 弹出栈顶节点并访问它。
3. 如果该节点有右子树，则将右子树节点入栈。
4. 重复步骤2和3，直到栈为空。

下面是C++代码实现：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur != nullptr || !s.empty()) {
        while (cur != nullptr) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        // 访问节点
        cout << cur->val << " ";
        cur = cur->right;
    }
}

其中，`TreeNode`是二叉树节点的结构体，包含`val`、`left`和`right`三个成员变量。

相关问题

二叉树 非递归中序遍历 c语言

二叉树的非递归中序遍历是指访问所有节点的一种方法，遵循“左根右”的顺序，即先遍历左子树，然后访问根节点，最后遍历右子树。在C语言中，我们可以利用栈数据结构实现这个过程，避免了直接使用递归带来的函数调用开销。

以下是C语言非递归实现二叉树中序遍历的基本步骤：

1. 定义一个结构体来表示二叉树节点，包含值、左右指针；
2. 创建一个空栈，用于存放待访问的节点；
3. 如果当前节点不为空：
a. 先将左子节点压入栈中，因为我们要先访问左子树；
b. 然后访问当前节点（打印或存储节点值）；
c. 再弹出栈顶元素，继续处理其右子节点，直到右子节点为空。
4. 当栈为空且所有节点都处理完毕，遍历结束。

#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*> s;
    TreeNode* curr = root;
    
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        
        curr = s.top();
        printf("%d ", curr->val); // 打印节点值
        s.pop();
        curr = curr->right;
    }
}

// 示例：
TreeNode* createTree() { ... } // 根据需要创建二叉树

int main() {
    TreeNode* root = createTree();
    inorderTraversal(root);
    return 0;
}

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

以下是二叉树非递归中序遍历的C语言实现：

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

// 定义栈结构体
typedef struct Stack {
    TreeNode** arr;
    int top;
    int maxSize;
} Stack;

// 创建栈
Stack* createStack(int size) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->arr = (TreeNode**)malloc(sizeof(TreeNode*) * size);
    stack->top = -1;
    stack->maxSize = size;
    return stack;
}

// 入栈
void push(Stack* stack, TreeNode* node) {
    if (stack->top == stack->maxSize - 1) {
        return;
    }
    stack->arr[++stack->top] = node;
}

// 出栈
TreeNode* pop(Stack* stack) {
    if (stack->top == -1) {
        return NULL;
    }
    return stack->arr[stack->top--];
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 中序遍历
int* inorderTraversal(TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* res = (int*)malloc(sizeof(int));
    Stack* stack = createStack(100); // 创建栈
    TreeNode* cur = root;
    while (cur != NULL || !isEmpty(stack)) {
        while (cur != NULL) { // 遍历左子树并入栈
            push(stack, cur);
            cur = cur->left;
        }
        cur = pop(stack); // 左子树遍历完毕，出栈一个节点
        res = (int*)realloc(res, sizeof(int) * (*returnSize + 1));
        res[(*returnSize)++] = cur->val; // 将出栈节点的值加入结果数组
        cur = cur->right; // 遍历右子树
    }
    return res;
}

该实现利用栈来模拟递归的过程，将待遍历的节点入栈，遍历完左子树后出栈一个节点，将其值加入结果数组，然后遍历其右子树。重复以上步骤直到栈为空。