二叉树中序遍历算法实现 (递归和非递归)

本文将介绍两种常用的二叉树中序遍历算法：递归和非递归，并提供完整的 C 语言代码实现，方便读者理解和学习。

1. 递归实现

递归方法是一种简洁直观的实现方式，它利用函数调用自身来实现遍历过程。

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

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

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

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

2. 非递归实现

非递归方法使用栈来模拟递归过程，避免了递归带来的函数调用开销，效率更高。

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

#define MAXSIZE 100 // 栈的最大容量

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

typedef struct stack {
    TNode *data[MAXSIZE];
    int top;
} Stack;

void InitStack(Stack *S) {
    S->top = -1;
}

int EmptyStack(Stack *S) {
    if (S->top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}

int PushStack(Stack *S, TNode *p) {
    if (S->top == MAXSIZE - 1) {
        return 0;
    }
    else {
        S->top++;
        S->data[S->top] = p;
        return 1;
    }
}

TNode *PopStack(Stack *S) {
    if (EmptyStack(S)) {
        return NULL;
    }
    else {
        TNode *p = S->data[S->top];
        S->top--;
        return p;
    }
}

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

void InOrder2(TNode *tree) {
    TNode *p = tree;
    Stack 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);
}

3. 完整代码

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

#define MAXSIZE 100 // 栈的最大容量

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

typedef struct stack {
    TNode *data[MAXSIZE];
    int top;
} Stack;

void InitStack(Stack *S) {
    S->top = -1;
}

int EmptyStack(Stack *S) {
    if (S->top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}

int PushStack(Stack *S, TNode *p) {
    if (S->top == MAXSIZE - 1) {
        return 0;
    }
    else {
        S->top++;
        S->data[S->top] = p;
        return 1;
    }
}

TNode *PopStack(Stack *S) {
    if (EmptyStack(S)) {
        return NULL;
    }
    else {
        TNode *p = S->data[S->top];
        S->top--;
        return p;
    }
}

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

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

void InOrder2(TNode *tree) {
    TNode *p = tree;
    Stack 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 *tree = (TNode *)malloc(sizeof(TNode));
    tree->data = 1;
    tree->Lsubtree = (TNode *)malloc(sizeof(TNode));
    tree->Rsubtree = (TNode *)malloc(sizeof(TNode));
    tree->Lsubtree->data = 2;
    tree->Lsubtree->Lsubtree = (TNode *)malloc(sizeof(TNode));
    tree->Lsubtree->Rsubtree = NULL;
    tree->Lsubtree->Lsubtree->data = 4;
    tree->Lsubtree->Lsubtree->Lsubtree = NULL;
    tree->Lsubtree->Lsubtree->Rsubtree = NULL;
    tree->Rsubtree->data = 3;
    tree->Rsubtree->Lsubtree = NULL;
    tree->Rsubtree->Rsubtree = NULL;

    printf("递归中序遍历结果：");
    InOrder(tree);
    printf("\n");

    printf("非递归中序遍历结果：");
    InOrder2(tree);
    printf("\n");

    return 0;
}

4. 总结

本文介绍了二叉树中序遍历的两种实现方式：递归和非递归，并提供了完整的代码示例。递归方法简洁易懂，但效率较低；非递归方法效率更高，但代码相对复杂。根据实际情况选择合适的算法实现。