二叉树的非递归遍历

2019-11-06 09:16:25

字体：大中小

来源：转载

供稿：网友

void PReOrder(BinTree *root) //非递归前序遍历 { stack<BinTree*> s; BinTree *p=root; while(p!=NULL||!s.empty()) { while(p!=NULL) { cout<<p->data<<" "; s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); s.pop(); p=p->rchild; } }}void inOrder(BinTree *root) //非递归中序遍历{ stack<BinTree*> s; BinTree *p=root; while(p!=NULL||!s.empty()) { while(p!=NULL) { s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); cout<<p->data<<" "; s.pop(); p=p->rchild; } } }void postOrder(BinTree *root) //非递归后序遍历{ if(root == NULL) return res; BinTree *p = root; stack<BinTree *> s; BinTree *last = NULL; s.push(p); while (!s.empty()) { p = s.top(); if( (p->left == NULL && p->right == NULL) || (p->right == NULL && last == p->left) || (last == p->right) ) { cout<<p->data<<" "; last = p; s.pop(); } else { if(p->right) s.push(p->right); if(p->left) s.push(p->left); } }}

上一篇：MP4学习（四）ts-mp4源码阅读（2）MP4的解析流程

下一篇：Codeforces 779B-Weird Rounding