二叉树的遍历（非递归）

二叉树的非递归遍历主要是利用栈的特性

 

void PreOrderTraverse(TNode *pRoot)//前序 { stack<TNode*> sck; sck.push(pRoot); TNode *pNode = nullptr; while(!sck.empty()) { pNode = sck.top(); sck.pop(); if(pNode != nullptr) { cout << pNode->val; sck.push(pNode->right); sck.push(pNode->left); } } } void InOrderTraverse(TNode *proot)//中序 { stack<TNode*> sck; TNode *pcur=proot; while(!sck.empty()||pcur!=NULL) { while(pcur!=NULL) { sck.push(pcur); pcur=pcur->left; } pcur=sck.top(); sck.pop(); cout<<pcur->val; if(pcur->right!=NULL) { pcur=pcur->right;// } else pcur=NULL; } } //后序遍历 //要设置一个标记，标记根节点。 typedef struct Gnode { TNode *node; bool isfirst; }Gnode; void PostOrderTraverse(TNode *proot) { stack<Gnode*> sck; TNode *pcur=proot; Gnode *tmp=NULL; while(!sck.empty()||pcur!=NULL) { while(pcur!=NULL) { Gnode *p=new Gnode; p->node=pcur; p->isfirst=true; pcur=pcur->left; sck.push(p); } tmp=sck.top(); if(tmp->isfirst==true) { tmp->isfirst=false; pcur=tmp->node->right;// } else { sck.pop(); cout<<tmp->node->val; pcur=NULL; } } }