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

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

递归中序遍历

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

非递归中序遍历

In0rder2(TNode *tree)
{
p = tree;
InitStack( S );
do {
while(p != NULL )
{
PushStack(S, p);
p = p->Lsubtree;
}
if ( not EmptyStack( S ) )
{
p = PopStack( S );
Access(p->data);
p = p->Rsubtree;
}
} while(not EmptyStack(S) or p != NULL);
}

主函数示例

int main(){
    TNode *tree = NULL; // 声明一棵树，并初始化为空
    // TODO: 在这里构建一棵二叉树
    // ...

    // 使用递归中序遍历输出树的节点值
    cout << '递归中序遍历: '; 
    InOrder(tree);
    cout << endl;

    // 使用非递归中序遍历输出树的节点值
    cout << '非递归中序遍历: '; 
    InOrder2(tree);
    cout << endl;

    return 0;
}

注意：

这里假设 TNode 结构体包含 data、Lsubtree 和 Rsubtree 三个成员变量，分别代表节点值、左子树和右子树。
Access(p->data) 函数用于访问节点的值，具体实现需根据实际情况进行调整。
InitStack(S)、PushStack(S, p)、PopStack(S)、EmptyStack(S) 分别用于初始化、入栈、出栈和判断栈是否为空的操作，具体实现需根据选择的栈数据结构进行调整。
在主函数中，需要根据实际情况构建一棵二叉树。

本示例代码仅供参考，读者可根据实际需求进行修改和完善。