二叉树中序遍历的递归与非递归实现

本文将介绍二叉树中序遍历的两种实现方式：递归和非递归，并提供相应的代码示例。

1. 递归实现

递归实现中序遍历的核心思想是：

访问左子树；
访问根节点；
访问右子树。

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

2. 非递归实现

非递归实现中序遍历需要借助栈来存储节点信息。算法流程如下：

初始化栈 S；
将当前节点 p 指向根节点；
循环遍历：
- 当 p 不为空时，将 p 入栈，并将 p 指向其左子树；
- 当栈不为空时，出栈一个节点 p，访问 p 的数据，并将 p 指向其右子树；
循环结束，遍历完成。

In0rder2(TNode *tree) {
  TNode *p = tree;
  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. 主函数代码

void main() {
  TNode *tree = createTree(); // 创建一棵二叉树
  InOrder1(tree); // 使用递归方式中序遍历二叉树
  printf("\n");
  InOrder2(tree); // 使用非递归方式中序遍历二叉树
}

上述代码中，createTree() 函数用于创建一棵二叉树，Access() 函数用于访问节点数据，InitStack(), PushStack(), PopStack(), EmptyStack() 函数分别用于初始化栈、入栈、出栈和判断栈是否为空。

通过以上代码示例，可以清晰地理解二叉树中序遍历的递归和非递归实现方式。