C语言用非递归实现二叉排序树的中序遍历，用代码显示出来

请问您的问题是关于C语言非递归实现二叉排序树的中序遍历，对吗？如果是，以下是一份代码示例：

void inorder(TreeNode* root) {
if (!root) return;

stack<TreeNode*> s;
TreeNode* p = root;

while (!s.empty() || p) {
if (p) {
s.push(p);
p = p->left;
} else {
p = s.top();
s.pop();
printf("%d ", p->val);
p = p->right;
}
}
}

如果您还有其他问题，请直接问我吧！如果您想听个笑话的话，我可以告诉您：“为什么听取别人的建议很重要？因为他们可能比你更聪明，当然，也可能比你更蠢！”

相关问题

c语言建立以左右孩子链接结构表示的二叉树,实现二叉树的先序、中序、后序的递归和非递归方式遍历,分层遍历、统计树的高度。 选做内容: 在二叉排序树中进行结点的插入和删除操作。

以下是基于左右孩子链接结构的二叉树的C语言代码实现：

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

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

// 创建二叉树
TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 先序递归遍历
void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}

// 中序递归遍历
void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->val);
    inOrder(root->right);
}

// 后序递归遍历
void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->val);
}

// 先序非递归遍历
void preOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        TreeNode* node = stack[top--];
        printf("%d ", node->val);
        if (node->right != NULL) {
            stack[++top] = node->right;
        }
        if (node->left != NULL) {
            stack[++top] = node->left;
        }
    }
}

// 中序非递归遍历
void inOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    TreeNode* p = root;
    while (p != NULL || top >= 0) {
        if (p != NULL) {
            stack[++top] = p;
            p = p->left;
        } else {
            p = stack[top--];
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

// 后序非递归遍历
void postOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top1 = -1;
    int top2 = -1;
    stack[++top1] = root;
    while (top1 >= 0) {
        TreeNode* node = stack[top1--];
        stack[++top2] = node;
        if (node->left != NULL) {
            stack[++top1] = node->left;
        }
        if (node->right != NULL) {
            stack[++top1] = node->right;
        }
    }
    while (top2 >= 0) {
        printf("%d ", stack[top2--]->val);
    }
}

// 分层遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* queue[100];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* node = queue[front++];
        printf("%d ", node->val);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
}

// 统计树的高度
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 二叉排序树中插入节点
TreeNode* insertNode(TreeNode* root, int val) {
    if (root == NULL) {
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else if (val > root->val) {
        root->right = insertNode(root->right, val);
    }
    return root;
}

// 二叉排序树中删除节点
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (val < root->val) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        TreeNode* minNode = root->right;
        while (minNode->left != NULL) {
            minNode = minNode->left;
        }
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    return root;
}

int main() {
    TreeNode* root = createTree();
    printf("先序递归遍历：");
    preOrder(root);
    printf("\n中序递归遍历：");
    inOrder(root);
    printf("\n后序递归遍历：");
    postOrder(root);
    printf("\n先序非递归遍历：");
    preOrderNonRecursive(root);
    printf("\n中序非递归遍历：");
    inOrderNonRecursive(root);
    printf("\n后序非递归遍历：");
    postOrderNonRecursive(root);
    printf("\n分层遍历：");
    levelOrder(root);
    printf("\n树的高度：%d\n", getHeight(root));
    root = insertNode(root, 10);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    printf("插入节点后的中序遍历：");
    inOrder(root);
    root = deleteNode(root, 10);
    printf("\n删除节点后的中序遍历：");
    inOrder(root);
    return 0;
}

设二叉树以二叉链表形式存放，用类C语言设计非递归算法判断一棵根结点为T的二叉树是否为二叉排序树。

可以采用中序遍历的方法来判断一棵二叉树是否为二叉排序树。中序遍历的结果应该是一个递增的序列，如果不是递增的，则不是二叉排序树。

具体实现如下：

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

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

// 定义栈结构体
typedef struct Stack {
    TreeNode *node;
    struct Stack *next;
} Stack;

// 创建节点
TreeNode* createNode(int val) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入节点
TreeNode* insertNode(TreeNode *node, int val) {
    if (node == NULL) {
        node = createNode(val);
        return node;
    }
    if (node->val > val) {
        node->left = insertNode(node->left, val);
    } else {
        node->right = insertNode(node->right, val);
    }
    return node;
}

// 创建栈
Stack* createStack() {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->node = NULL;
    stack->next = NULL;
    return stack;
}

// 入栈
void push(Stack *stack, TreeNode *node) {
    Stack *newNode = createStack();
    newNode->node = node;
    newNode->next = stack->next;
    stack->next = newNode;
}

// 出栈
TreeNode* pop(Stack *stack) {
    if (stack->next == NULL) {
        return NULL;
    }
    TreeNode *node = stack->next->node;
    stack->next = stack->next->next;
    return node;
}

// 非递归中序遍历
int isBST(TreeNode *root) {
    if (root == NULL) {
        return 1;
    }
    Stack *stack = createStack();
    TreeNode *node = root;
    int flag = 1;
    int pre = node->val;
    while (node != NULL || stack->next != NULL) {
        while (node != NULL) {
            push(stack, node);
            node = node->left;
        }
        node = pop(stack);
        if (node->val < pre) {
            flag = 0;
            break;
        }
        pre = node->val;
        node = node->right;
    }
    return flag;
}

// 测试代码
int main() {
    // 构建二叉树
    TreeNode *root = createNode(4);
    insertNode(root, 2);
    insertNode(root, 6);
    insertNode(root, 1);
    insertNode(root, 3);
    insertNode(root, 5);
    insertNode(root, 7);
    // 判断是否为二叉排序树
    int flag = isBST(root);
    if (flag) {
        printf("This is a Binary Search Tree.\n");
    } else {
        printf("This is not a Binary Search Tree.\n");
    }
    return 0;
}

这里我们使用了一个栈来保存遍历的节点，用一个变量pre来保存上一个节点的值，从而判断是否递增。这个算法的时间复杂度为O(n)，空间复杂度为O(h)，其中h为树的高度。