二叉树中序遍历：递归与非递归实现详解

这段代码实现了二叉树的中序遍历，分别用递归和非递归的方法实现。

typedef struct TNode
 {
  ElemType data; //数据元素 
  struct TNode * Lsubtree; //左子树 
  struct TNode * Rsubtree; //右子树 
 }TNode, *pTNode;

void InOrder1(TNode *tree)
{
     if (tree != NULL)
         {
           InOrder1(tree->Lsubtree);
           printf('%d ', tree->data);
           InOrder1(tree->Rsubtree);
          }
}

void InOrder2(TNode *tree)
{
   TNode *p = tree; //p指向当前结点
   InitStack(S);
   do {
         while (p != NULL) { //一直向左并将沿途结点入栈
                                      PushStack(S, p);
                                      p = p->Lsubtree;
         }
        if (!EmptyStack(S))
            {
             p = PopStack(S); //结点弹出栈顶
             printf('%d ', p->data); //访问该结点
             p = p->Rsubtree; //转向右子树
             }
         } 
    while (!EmptyStack(S) || p != NULL);
}

函数InOrder1使用递归的方式，首先判断当前节点是否为空，如果不为空则递归遍历左子树，输出当前节点的数据元素，再递归遍历右子树。

函数InOrder2使用非递归的方式，首先将根节点压入栈中，然后不断向左子树遍历并将沿途结点入栈，直到p为空。然后弹出栈顶元素，访问该结点的数据元素，再将p指向右子树。如果栈不为空或p不为空，则继续遍历。

两种方法的时间复杂度均为O(n)，但递归方法的空间复杂度较高，非递归方法使用栈存储结点，空间复杂度较低。