讨论：二叉树的构造(先序，中序，后序非递归算法)
我想这都是一个很老很老的话题了吧！但是我在网上找了找，通过先序...非递归算法构造二叉树的方法真没发现多少，倒是到处都是遍历的不同办法，也许你要说，遍历过程中就可以实现二叉树的构造！但是我认为这中间还是有很多不同的，对于构造二叉树，只要制定了规则，就可以很容易写出代码！但是不同的规则，对应着不同算法，算法的复杂度，优化程度也是不一样的！这就需要去讨论，所以在这里希望大家把心中的想法写出来，你可以不屑一故，你也可以在心里默默的说这就是个SB，但是请你不要直接发上来了，我需要的是大家不同的想法！但
在我看来，先序，中序和后序，只需解决了其中一种另外两种可以仿照写出！下面就请大家只谈谈用先序构造二叉树的规则(有了规则自然就有算法）吧，主要就是怎么判断是右子树还是左子树？怎么回溯？
我自己先来说说吧，有什么不对的地方还请指教！
有两种解决办法：
第一种是运用队列，对入队的数据编号（按满二叉树读数）,当为空时还是要入队，然后运用满二叉树的特点，假如第i层双亲编号为n，则其位于i+1层上的左孩子的编号为2n，右孩子的编号为2n+1！
第二种是运用栈(栈里边放节点指针）：判断链接为左孩子的规则是：栈顶元素不为空
判断链接为右孩子的规则是：栈顶元素为空，然后弹栈（假设弹出指针为S），直到S->rchild=NULL，及把产生的节点T，链接在S的右孩子上；
回溯的规则是：（实际上判断链接为右孩子的过程中就有回溯），这个地方的回溯是遇到叶子回溯，栈顶元素为空，且输入的数据（这儿的数据就是二叉树节点的数据域）为空，则把栈顶元素弹出！
以上就是我的大概思路，请大家说说自己的想法吧!
[解决办法]
呵呵，不采用递归建树不是也有现成的算法吗？
[解决办法]
LZ可以告诉我二叉树的三个序的非递归算法怎么写吗 谢谢了
[解决办法]
你要一种就给你一种吧！用栈实现的。
void preorder_non_recursive(node *root) //前序遍历的非递归实现{ stack<node*> S; node *temp = root; S.push(temp); while(!S.empty()) { temp = S.top(); S.pop(); cout<<temp->data; if(temp->right != NULL) S.push(temp->right); if(temp->left != NULL) S.push(temp->left); }}