二叉树中序遍历代码实现及解析

本文提供两种二叉树中序遍历代码实现，包括递归和非递归方法，并附带完整主函数代码示例，方便读者理解和学习二叉树遍历算法。

递归方法

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

typedef struct TNode {
    int data;
    struct TNode *Lsubtree;
    struct TNode *Rsubtree;
} TNode;

void Access(int data) {
    printf("%d ", data);
}

void InOrder1(TNode *tree) {
    if (tree != NULL) {
        InOrder1(tree->Lsubtree);
        Access(tree->data);
        InOrder1(tree->Rsubtree);
    }
}

非递归方法

void InitStack(TNode **S) {
    *S = NULL;
}

int EmptyStack(TNode *S) {
    return S == NULL;
}

void PushStack(TNode **S, TNode *p) {
    p->Rsubtree = *S;
    *S = p;
}

TNode *PopStack(TNode **S) {
    TNode *p = *S;
    *S = p->Rsubtree;
    return p;
}

void InOrder2(TNode *tree) {
    TNode *p = tree;
    TNode *S;
    InitStack(&S);
    do {
        while (p != NULL) {
            PushStack(&S, p);
            p = p->Lsubtree;
        }
        if (!EmptyStack(S)) {
            p = PopStack(&S);
            Access(p->data);
            p = p->Rsubtree;
        }
    } while (!EmptyStack(S) || p != NULL);
}

完整主函数代码

int main() {
    TNode node1, node2, node3, node4, node5, node6;
    node1.data = 1;
    node2.data = 2;
    node3.data = 3;
    node4.data = 4;
    node5.data = 5;
    node6.data = 6;
    node1.Lsubtree = &node2;
    node1.Rsubtree = &node3;
    node2.Lsubtree = &node4;
    node2.Rsubtree = NULL;
    node3.Lsubtree = &node5;
    node3.Rsubtree = &node6;
    node4.Lsubtree = NULL;
    node4.Rsubtree = NULL;
    node5.Lsubtree = NULL;
    node5.Rsubtree = NULL;
    node6.Lsubtree = NULL;
    node6.Rsubtree = NULL;

    printf("InOrder1: ");
    InOrder1(&node1);
    printf("\n");

    printf("InOrder2: ");
    InOrder2(&node1);
    printf("\n");

    return 0;
}

代码解析

递归方法

递归方法的思路是：

1. 递归访问左子树
2. 访问当前节点
3. 递归访问右子树

非递归方法

非递归方法使用栈来模拟递归过程，具体步骤如下：

1. 初始化栈
2. 将当前节点入栈
3. 如果当前节点不为空，则将当前节点的左子节点入栈，并将当前节点指向左子节点，重复步骤 3
4. 如果当前节点为空，则出栈，访问出栈节点的值，并将当前节点指向出栈节点的右子节点，重复步骤 3
5. 重复步骤 3-4 直到栈为空且当前节点为空

总结

本文介绍了两种二叉树中序遍历方法：递归和非递归。递归方法简单易懂，但递归深度过大会导致栈溢出；非递归方法使用栈来模拟递归过程，可以避免栈溢出问题，但代码实现较为复杂。选择哪种方法取决于具体应用场景。