中序创建二叉树，用非递归遍历二叉树

中序创建二叉树的步骤如下：
1. 如果当前节点为空，则新建一个节点，并将其赋值为根节点。
2. 如果当前节点不为空，则将其与待插入节点的值进行比较。
3. 如果待插入节点的值小于当前节点的值，则将其插入到当前节点的左子树中。
4. 如果待插入节点的值大于当前节点的值，则将其插入到当前节点的右子树中。
5. 重复步骤2-4，直到找到一个空节点为止。

非递归遍历二叉树的步骤如下：
1. 创建一个栈，并将根节点入栈。
2. 当栈不为空时，取出栈顶元素，并将其左子树中的所有节点入栈。
3. 重复步骤2，直到左子树为空。
4. 取出栈顶元素，并将其右子树入栈。
5. 重复步骤2-4，直到栈为空。

相关问题

c++实现以下功能1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树1 4.中序遍历二叉树2 5.后序遍历二叉树 6.层序遍历二叉树 7.求二叉树的深度 8.退出

C++可以通过定义二叉树节点结构体以及相应的函数来实现以上功能：

1. 创建二叉树：可以通过递归或者非递归方式实现，具体实现方式可以根据需求选择。递归方式实现时，可以采用前序遍历的方式，先创建根节点，再分别创建左右子树；非递归方式可以采用层序遍历的方式，从上到下、从左到右依次创建节点。

2. 先序遍历二叉树：先输出当前节点的值，再遍历左子树，最后遍历右子树。

3. 中序遍历二叉树1：先遍历左子树，再输出当前节点的值，最后遍历右子树。

4. 中序遍历二叉树2：采用非递归方式实现时，需要借助栈数据结构。从根节点开始，将左子树节点依次入栈，然后出栈，输出当前节点的值，再将右子树入栈。

5. 后序遍历二叉树：先遍历左子树，再遍历右子树，最后输出当前节点的值。

6. 层序遍历二叉树：从上到下、从左到右依次遍历每一层节点。

7. 求二叉树的深度：可以采用递归方式求解，分别求出左子树和右子树的深度，然后取较大值加1即为二叉树的深度。

8. 退出：程序结束。

写C语言二叉树中序非递归遍历代码

以下是C语言二叉树中序非递归遍历代码：

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

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

// 定义栈结构体
struct Stack {
    struct TreeNode** data;
    int top;
    int size;
};

// 初始化栈
void init_stack(struct Stack* s, int size) {
    s->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * size);
    s->top = -1;
    s->size = size;
}

// 入栈
void push(struct Stack* s, struct TreeNode* val) {
    if (s->top == s->size - 1) {
        return;
    }
    s->top++;
    s->data[s->top] = val;
}

// 出栈
struct TreeNode* pop(struct Stack* s) {
    if (s->top == -1) {
        return NULL;
    }
    struct TreeNode* val = s->data[s->top];
    s->top--;
    return val;
}

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

// 中序遍历
void inorder_traversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct Stack s;
    init_stack(&s, 100);
    struct TreeNode* cur = root;
    while (cur != NULL || !is_empty(&s)) {
        while (cur != NULL) {
            push(&s, cur);
            cur = cur->left;
        }
        cur = pop(&s);
        printf("%d ", cur->val);
        cur = cur->right;
    }
}

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

    // 中序遍历
    inorder_traversal(root);

    return 0;
}

在这段代码中，我们首先定义了二叉树结构体 `TreeNode` 和栈结构体 `Stack`。其中，`TreeNode` 包含节点的值以及左右子树指针，`Stack` 包含数据指针、栈顶指针以及栈的大小。我们还定义了一些栈的操作函数，包括初始化栈、入栈、出栈、以及判断栈是否为空。

在 `inorder_traversal` 函数中，我们使用栈来实现中序遍历。具体来说，我们首先将根节点入栈，然后将左子树的所有节点入栈。当左子树遍历完毕后，我们将栈顶节点出栈并打印其值，然后将当前节点指向右子树。如果右子树不为空，则将右子树入栈，继续遍历右子树的左子树。整个过程一直持续到栈为空为止。

最后，在 `main` 函数中，我们构造了一棵二叉树，并进行了中序遍历。