递归完成树的遍历很好理解，倘若是非递归，不要告诉我算法导论上有，我要maker的思考过程 既然递归能够实现，那就模拟递归。递归的本质就是压栈。 首先简单树，观察递归的压栈过程
A、B即使节点的数据也代表节点的地址。 对这棵树使用递归完成前序创建
;struct treenode;typedef struct treenode* TREE;struct treenode{ char data; TREE left; TREE right;};void tree_front(TREE& T){ char buff; cout<<“please input ,or NULL(*)”<<endl; cin>>buff; if(buff!=’*’) { T=new struct treenode; if(T==NULL) exit(-1); T->data=buff; tree_front(T->left); tree_front(T->right); } else T=NULL;}int main(){ TREE T; tree_front(T); return 0;}
树建立起来
那么研究一下这个栈的调用过程
利用vs2008的反汇编窗口来看 1、进入main第一次调用函数 tree_front(T); 0084162E leaeax,[T] 00841631 pusheax 00841632 calltree_front (8410B4h) //称为函数1 00841637 addesp,4 将T的地址传入函数 2、第一次进入函数1后 输入A，在在调用自身函数之前 tree_front(T->left); 0084156D moveax,dword ptr [T] 00841570 movecx,dword ptr [eax] 00841572 addecx,4 00841575 pushecx 00841576 calltree_front (8410B4h) //称为函数2 0084157B addesp,4 将A地址压栈 3、进入递归调用函数2 输入B，在在调用自身函数之前 tree_front(T->left); 0084156D moveax,dword ptr [T] 00841570 movecx,dword ptr [eax] 00841572 addecx,4 00841575 pushecx 00841576 calltree_front (8410B4h) //称为函数3 0084157B addesp,4 将B压栈 4、进入递归调用函数3 输入×，表示输入NULL T=NULL; 00841591 moveax,dword ptr [T] 00841594 movdword ptr [eax],0 返回调用函数3的地方 执行下一条指令 0084157B addesp,4 就是出栈，将B出栈 准备进入右子树调用函数 5、进入递归右子树调用函数 tree_front(T->right); 0084157E moveax,dword ptr [T] 00841581 movecx,dword ptr [eax] 00841583 addecx,8 00841586 pushecx 00841587 calltree_front (8410B4h) //称为函数4 0084158C addesp,4 此时又将B压栈 6、进入递归调用函数4 输入×，表示输入NULL T=NULL; 00841591 moveax,dword ptr [T] 00841594 movdword ptr [eax],0 返回函数4，执行下一条指令 0084158C addesp,4 将B出栈，这时，将从函数2出来，进入函数2的下一条右子树的调用 7、进入函数2的下一条右子树的调用 输入×，执行 T=NULL; 00841591 moveax,dword ptr [T] 00841594 movdword ptr [eax],0 然后退出函数，执行下一条指令、 。。。。 知道最后完成 用一个调用图来表示
分析一下这个栈的情况 不管是节点A还是节点B，在进入左子树时，都会将本节点的地址保存起来，以便返回 所以可以用vector容器来模拟这个压入过程
初始一些变量 struct treenode; typedef struct treenode* TREE;
struct treenode { char data; TREE left; TREE right; };
则原始非递归前序遍历的伪代码为
void preorder(TREE T) { while(1) { 访问节点T； 压栈T； T=T->left（T变成将左子树） } } 完成上图A到B的遍历， B的做节点为NULL这时，应该pop出B节点 然后将B的右子树作为新的节点 然后修改伪代码 void preorder(TREE T) { while(1) { if(T!=NULL) { 访问节点T； 压栈T； T=T->left（T变成将左子树） } else { T=出栈； T=T->right; } } } 出栈就是出现在遍历到左子树为NULL时，根据最新入栈的节点，切换到右子树 右子树为NULL时回到父树的父树，然后变成，父树父树的右子树。
再考虑，while的结束条件，观察图中，A的右子树返回时，遍历结束，此时栈中不再包含A、B的节点， 修改伪代码 void preorder(TREE T) { 初始化栈； while(栈不为空) { if(T!=NULL) { 访问节点T； 压栈T； T=T->left（T变成将左子树） } else { T=出栈； T=T->right; } } } 条件还是有个bug，当A左子树返回时，栈就为空了，但是此时还要遍历A的右子树
看看整个树遍历时，栈的情况
栈空有三处，所以还要加上一个条件 这里有的变量就是节点，，所以上次栈空时对应的节点情况 有效->有效->空（最后一个右子树） 而要退出是在最后一个栈空时，根据逻辑判断，两者相与 修改伪代码 void preorder(TREE T) { 初始化栈； while(栈不为空 || 节点不为NULL) { if(T!=NULL) { 访问节点T； 压栈T； T=T->left（T变成将左子树） } else { T=出栈； T=T->right; } } }
答：他是憋死的，因为沙漠里没有电线杆撒尿。问：
