用c➕➕实现中序遍历二叉树T的非递归算法

好的，下面是使用 C++ 实现中序遍历二叉树T的非递归算法的代码，同样假设二叉树节点类型为TreeNode，具有val、left、right三个属性：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    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();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

该算法与之前的 Java 实现类似，同样使用了一个栈来辅助遍历。不同的是，使用 C++ 需要注意一些细节，如栈的声明方式为 stack<TreeNode*>，表示存储指向 TreeNode 对象的指针；访问 TreeNode 的属性需要使用箭头符号 ->。

相关问题

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

中序遍历二叉树的非递归算法需要用到栈，具体步骤如下：

1. 初始化一个空栈和一个指向根节点的指针p。

2. 如果p不为NULL或者栈不为空，则进行循环，循环条件为p不为NULL或者栈不为空。

3. 在循环中，将p指向的节点以及p的左子树节点依次入栈，直到p为NULL。

4. 弹出栈顶元素，输出该元素的值，并将p指向该元素的右子树节点。

5. 循环回到第2步。

C语言实现如下：

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorderTraversal(struct TreeNode* root) {
    struct TreeNode* stack[1000]; // 定义栈
    int top = -1; // 栈顶指针初始化为-1
    struct TreeNode* p = root;

    while (p != NULL || top != -1) { // 循环条件
        while (p != NULL) { // 将p节点以及左子树节点入栈
            stack[++top] = p;
            p = p->left;
        }

        if (top != -1) { // 弹出栈顶元素，输出该元素的值，并将p指向该元素的右子树节点
            p = stack[top--];
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

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

中序遍历二叉树的非递归算法可以借助栈来实现。具体步骤如下：

1. 创建一个空栈。
2. 将根节点入栈。
3. 当栈非空时，重复以下步骤：
- 将栈顶节点出栈，输出它的值。
- 如果该节点有右子树，则将右子树入栈。
- 如果该节点没有右子树且有左子树，则将左子树入栈。
4. 当栈为空时，遍历结束。

下面是该算法的 C 语言实现：

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

// 定义二叉树节点结构体
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node, *Tree;

// 定义栈结构体
typedef struct Stack {
    Node *data[100]; // 栈的最大容量为 100
    int top; // 栈顶指针
} Stack;

// 初始化栈
void init(Stack *s) {
    s->top = -1;
}

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

// 判断栈是否已满
int is_full(Stack *s) {
    return s->top == 99;
}

// 入栈
void push(Stack *s, Node *node) {
    if (is_full(s)) {
        printf("Error: Stack is full!\n");
        return;
    }
    s->top++;
    s->data[s->top] = node;
}

// 出栈
Node* pop(Stack *s) {
    if (is_empty(s)) {
        printf("Error: Stack is empty!\n");
        return NULL;
    }
    Node *node = s->data[s->top];
    s->top--;
    return node;
}

// 中序遍历二叉树的非递归算法
void inorder_traversal(Tree tree) {
    if (tree == NULL) {
        return;
    }
    Stack s;
    init(&s);
    Node *p = tree;
    while (p || !is_empty(&s)) {
        while (p) {
            push(&s, p);
            p = p->left;
        }
        if (!is_empty(&s)) {
            p = pop(&s);
            printf("%d ", p->data);
            p = p->right;
        }
    }
}

// 创建二叉树
Tree create_tree() {
    Tree tree;
    int data;
    scanf("%d", &data);
    if (data == -1) { // 输入 -1 表示该节点为空
        tree = NULL;
    } else {
        tree = (Tree)malloc(sizeof(Node));
        tree->data = data;
        tree->left = create_tree();
        tree->right = create_tree();
    }
    return tree;
}

int main() {
    Tree tree = create_tree();
    printf("中序遍历二叉树的结果为：\n");
    inorder_traversal(tree);
    printf("\n");
    return 0;
}

注意，这里的二叉树节点数据类型是 `Node`，而不是 `int`，因为每个节点包含了左右子树的指针。同时，这里的栈使用了数组实现，最大容量为 100，如果需要更大的容量可以根据实际情况进行修改。