c语言输出二叉树的中序遍历

以下是C语言输出二叉树中序遍历的代码：

#define MAX_STACK 50

void InOrderTraverse(BTree T) {
    BTree STACK[MAX_STACK], p = T;
    int top = -1;
    while (p != NULL || top != -1) {
        while (p != NULL) {
            STACK[++top] = p;
            p = p->lchild;
        }
        p = STACK[top--];
        VISIT(p);
        p = p->rchild;
    }
}

该算法使用了一个栈来模拟递归过程，实现了二叉树的中序遍历。具体实现过程是，先将根节点入栈，然后将左子树的所有节点入栈，直到左子树为空。此时弹出栈顶元素并访问，然后将指针指向右子树，继续重复上述过程，直到栈为空。

相关问题

二叉树中序遍历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 initStack(struct Stack *s, int size) {
    s->data = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * size);
    s->top = -1;
    s->size = size;
}

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

// 判断栈是否已满
int isFull(struct Stack *s) {
    return s->top == s->size - 1;
}

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

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

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

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

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

c语言二叉树先序遍历中序遍历

下面是C语言实现二叉树先序遍历和中序遍历的示例代码:

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

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

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

// 先序遍历二叉树
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);
}

int main() {
    // 创建二叉树
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    // 先序遍历二叉树
    printf("Preorder Traversal: ");
    preorder(root);
    printf("\n");

    // 中序遍历二叉树
    printf("Inorder Traversal: ");
    inorder(root);
    printf("\n");

    return 0;
}

输出结果为：

Preorder Traversal: 1 2 4 5 3 6 7
Inorder Traversal: 4 2 5 1 6 3 7

其中，先序遍历的顺序为：根结点 -> 左子树 -> 右子树；中序遍历的顺序为：左子树 -> 根结点 -> 右子树。