用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语言编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法，要有菜单

好的，以下是代码实现。注意，这里只提供代码参考，具体实现可能需要根据具体情况进行调整。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

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

void createTree(TreeNode** node){
    int val;
    scanf("%d",&val);
    if(val == -1){
        *node = NULL;
    }else{
        *node = (TreeNode*)malloc(sizeof(TreeNode));
        (*node)->val = val;
        createTree(&((*node)->left));
        createTree(&((*node)->right));
    }
}

void inOrderRecursive(TreeNode* node){
    if(node != NULL){
        inOrderRecursive(node->left);
        printf("%d ",node->val);
        inOrderRecursive(node->right);
    }
}

void postOrderRecursive(TreeNode* node){
    if(node != NULL){
        postOrderRecursive(node->left);
        postOrderRecursive(node->right);
        printf("%d ",node->val);
    }
}

void inOrderNonRecursive(TreeNode* node){
    TreeNode* stack[MAXSIZE];
    int top = -1;
    while(node != NULL || top != -1){
        while(node != NULL){
            stack[++top] = node;
            node = node->left;
        }
        if(top != -1){
            node = stack[top--];
            printf("%d ",node->val);
            node = node->right;
        }
    }
}

void postOrderNonRecursive(TreeNode* node){
    TreeNode* stack[MAXSIZE];
    int top = -1,visited[MAXSIZE] = {0};
    while(node != NULL || top != -1){
        while(node != NULL){
            stack[++top] = node;
            node = node->left;
        }
        if(top != -1){
            node = stack[top];
            if(visited[node->val]){
                printf("%d ",node->val);
                top--;
                node = NULL;
            }else{
                visited[node->val] = 1;
                node = node->right;
            }
        }
    }
}

int main(){
    TreeNode* root = NULL;
    int choice;
    while(1){
        printf("\n1. Create binary tree\n");
        printf("2. Inorder recursive traversal\n");
        printf("3. Postorder recursive traversal\n");
        printf("4. Inorder non-recursive traversal\n");
        printf("5. Postorder non-recursive traversal\n");
        printf("6. Exit\n");
        scanf("%d",&choice);
        switch(choice){
            case 1:
                printf("Enter tree in preorder: ");
                createTree(&root);
                break;
            case 2:
                printf("Inorder recursive traversal: ");
                inOrderRecursive(root);
                printf("\n");
                break;
            case 3:
                printf("Postorder recursive traversal: ");
                postOrderRecursive(root);
                printf("\n");
                break;
            case 4:
                printf("Inorder non-recursive traversal: ");
                inOrderNonRecursive(root);
                printf("\n");
                break;
            case 5:
                printf("Postorder non-recursive traversal: ");
                postOrderNonRecursive(root);
                printf("\n");
                break;
            case 6:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}

菜单功能：
1. 创建二叉树
2. 二叉树中序遍历的递归算法
3. 二叉树后续遍历的递归算法
4. 二叉树中序遍历的非递归算法
5. 二叉树后续遍历的非递归算法
6. 退出程序

用c语言编写一个非递归的中序遍历二叉树算法

在C语言中，非递归的中序遍历二叉树通常会采用栈的数据结构来辅助实现。下面是一个简单的示例：

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

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

// 助手函数，用于将当前节点压入栈
void pushIntoStack(TreeNode* root, StackNode** stack) {
    if (root == NULL) return;
    push(*stack, root);
    pushIntoStack(root->left, stack);
    pushIntoStack(root->right, stack);
}

// 助手函数，弹出栈顶元素并访问它
TreeNode* popAndVisit(StackNode** stack) {
    if (*stack->top == NULL) return NULL;
    TreeNode* node = (*stack)->top->data;
    (*stack)->top = (*stack)->top->next;
    return node;
}

// 中序遍历非递归版本
void inorderTraversalNonRecursive(TreeNode* root) {
    StackNode* stack = createStack(); // 初始化空栈
    TreeNode* current = root;
    
    while (current != NULL || !isEmpty(stack)) {
        while (current != NULL) {
            pushIntoStack(current, &stack);
            current = current->left;
        }
        
        current = popAndVisit(&stack); // 访问栈顶节点
        printf("%d ", current->val); // 输出节点值
        current = current->right; // 移动到右子树
    }

    destroyStack(stack); // 释放栈内存
}

int main() {
    // 创建二叉树并初始化...
    TreeNode* root = ...;
    inorderTraversalNonRecursive(root);
    return 0;
}

在这个例子中，我们首先创建一个栈，并将根节点及其所有左子节点压入栈。然后进入一个循环，只要栈不为空或者当前节点还有未访问的右子节点，就从栈顶取出一个节点访问，再将其右子节点压入栈。如此反复直到遍历完整棵树。