2叉树的递归与非递归遍历的源代码void main()
{
btnode *bt;
cout<<"请输入叉树:\n";
bt=inittree();
cout<<"\n递归先根遍历:";
prevt(bt);
cout<<"\n递归中根遍历:";
midvt(bt);
cout<<"\n递归后根遍历:";
lasvt(bt);
cout<<"\n非递归后根遍历:";
nprevt(bt);
cout<<"\n非递归后根遍历:";
nmidvt(bt);
cout<<"\n非递归后根遍历:";
nlasvt(bt);
cout<<endl;
}
二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树的遍历中，我们通常有三种基本的遍历方法：前序遍历（先根遍历）、中序遍历和后序遍历。这些遍历方法在不同的场景下有着不同的应用，例如数据结构的序列化、搜索算法的设计等。
1. **前序遍历（先根遍历）**：
- 递归实现：首先访问根节点，然后递归遍历左子树，最后遍历右子树。
- 非递归实现（使用栈）：首先将根节点压入栈，然后进入一个循环。如果当前节点不为空，就访问它并将其左子节点压入栈；否则，从栈中弹出一个节点，访问它，然后转向其右子节点。循环直到栈为空且当前节点为空。
2. **中序遍历**：
- 递归实现：首先遍历左子树，然后访问根节点，最后遍历右子树。
- 非递归实现（使用栈）：与前序遍历类似，但处理顺序不同。首先将根节点压入栈，然后进入循环。如果当前节点不为空，就将其压入栈并转向其左子节点；否则，从栈中弹出一个节点，访问它，然后如果它有右子节点，则转向右子节点。
3. **后序遍历（后根遍历）**：
- 递归实现：首先遍历左子树，然后遍历右子树，最后访问根节点。
- 非递归实现（使用两个栈）：后序遍历的非递归实现较为复杂，因为需要记住子节点的访问顺序。这里使用两个栈，一个用于存储节点，另一个用于记录访问顺序。首先将根节点压入栈1，并设置标志为1表示待访问左子节点；然后进入循环。如果当前节点不为空，就将其压入栈1，同时设置相应的标志，然后转向其左子节点。如果当前节点为空，就检查栈1是否为空。如果不为空，根据栈1顶部节点的标志决定是压入栈2还是访问该节点，然后根据标志更新当前节点。循环直到栈1和当前节点都为空。
给定的代码实现了以上三种遍历方法的递归和非递归版本。`inittree()` 函数用于从用户输入构建二叉树，而`prevt()`, `midvt()`, `lasvt()` 分别对应前序、中序和后序的递归遍历函数。非递归版本的函数`nprevt()`, `nmidvt()`, `nlasvt()` 则使用了栈来实现遍历，其中`nlasvt()` 使用了两个栈来处理后序遍历的特殊情况。
在主函数`main()` 中，程序会先让用户输入二叉树的结构，然后依次输出各种遍历的结果。注意，这里的代码没有处理异常，实际应用中应增加适当的错误处理机制。
二叉树的遍历是数据结构中的基础操作，递归和非递归方法各有优缺点。递归方法简洁直观，但当树的深度很大时可能会导致栈溢出。非递归方法则可以避免栈溢出，但实现相对复杂，需要使用额外的数据结构如栈来辅助遍历。
