2叉树非递归遍历 求拍
#include <stdio.h>#include <stack>typedef struct BiNode { int data; BiNode* lchild; BiNode* rchild;}BiNode,BiTree;enum Tags{left,right};BiTree* CreateTree(BiTree** t){ int data; scanf("%d",&data); if (data!=100) { (*t)=new BiNode(); (*t)->data = data; CreateTree(&((*t)->lchild)); CreateTree(&((*t)->rchild)); } return *t;}void ReleaseTree(BiTree* t){ if (t) { ReleaseTree(t->lchild); ReleaseTree(t->rchild); delete t; }}void InorderTraverseEX(BiTree* p){ std::stack<BiNode*> s; BiTree* t = p; while (t||!s.empty()) { if (t) { s.push(t); t=t->lchild; } else { printf("%d\n",s.top()->data); t=s.top(); t=t->rchild; s.pop(); } }}void PreorderTraverseEX(BiTree* t){ BiTree* p = t; std::stack<BiTree*> s; while (p||!s.empty()) { if (p) { printf("%d\n",p->data); s.push(p); p=p->lchild; } else { p=s.top(); p= p->rchild; s.pop(); } } }void PostorderTraverseEX(BiTree* t){ BiTree* p = t; std::stack<BiTree*> s; std::stack<Tags> sTag; while (true) { while (p!=NULL) { s.push(p); p=p->lchild; sTag.push(left); } while(sTag.top()==right) //使用while 是为了让 节点不用再向左延伸，以免重复。 { printf("%d\n",s.top()->data); p=s.top(); //这句强调的是 p 需要指向刚刚访问过的节点 s.pop(); sTag.pop(); if (s.empty()||sTag.empty()) return; } sTag.pop(); sTag.push(right); p=s.top()->rchild; }}int main(){ BiTree* t = new BiNode(); t = CreateTree(&t); printf("先序遍历\n"); PreorderTraverseEX(t); printf("中序遍历\n"); InorderTraverseEX(t); printf("后序遍历\n"); PostorderTraverseEX(t); ReleaseTree(t); return 0;}