二叉树的非递归遍历与递归建树.doc

void POrder(struct User* pRoot) /非递归前序调用 /（1）将根作为当前节点/（2）若当前节点不为空，则打印当前节点，并将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。/（3）否则，出栈一个元素，将当前节点置为当前节点的右儿子，循环直到当前节点为NULL或者栈为空。stack s1;struct User *pRootTemp=pRoot; /位置指针/（1）将根作为当前节点while(1)/（2）若当前节点不为空，则打印当前节点，并将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。if (pRootTemp!=NULL) printf(%s,pRootTemp-cName);s1.push(pRootTemp);pRootTemp=pRootTemp-pNext0;else/（3）否则，出栈一个元素，将当前节点置为当前节点的右儿子，循环直到当前节点为NULL或者栈为空。pRootTemp=s1.top();s1.pop();pRootTemp=pRootTemp-pNext1;if (pRootTemp=NULL) & (s1.empty() break;void MOrder(struct User* pRoot) /非递归完成中序遍历/（1）将根作为当前节点/（2）若当前节点不为空，则将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。/（3）否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。stack s1;struct User *pRootTemp=pRoot; /位置指针/（1）将根作为当前节点while(1)/（2）若当前节点不为空，则将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。if (pRootTemp!=NULL) s1.push(pRootTemp);pRootTemp=pRootTemp-pNext0;else/（3）否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。pRootTemp=s1.top();s1.pop();printf(%s ,pRootTemp-cName);pRootTemp=pRootTemp-pNext1;if (pRootTemp=NULL) & (s1.empty() break;void BOrder(struct User* pRoot) /非递归完成后序调用/（1）将根作为当前节点/（2）若当前节点不为空，则将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。/（3）否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。/在前面算法的基础上增加二次入栈的算法stack s1;struct User *pRootTemp=pRoot; /位置指针/（1）将根作为当前节点while(1)/（2）若当前节点不为空，则将当前节点入栈；将当前节点的左儿子赋给当前节点，循环。if (pRootTemp!=NULL) pRootTemp-isFirst=true;/第一次s1.push(pRootTemp);pRootTemp=pRootTemp-pNext0;else/（3）否则，出栈一个元素，打印这个节点，将当前节点置为当前节点的右儿子，循环(2),直到当前节点为NULL或者栈为空。pRootTemp=s1.top();s1.pop();if (pRootTemp-isFirst=true)pRootTemp-isFirst=false;s1.push(pRootTemp);/入栈右边的,也叫二次入栈pRootTemp=pRootTemp-pNext1;else/第二次出现才打印printf(%s ,pRootTemp-cName);pRootTemp=NULL;if (pRootTemp=NULL) & (s1.empty() break;先序创建二叉树：顺序为：A bd#e# cf#struct User* CreateBefore() char ch; ch=getchar(); struct User* root; if(ch=#) return NULL; else root=new struct User; root-cNa