C语言二叉树的非递归遍历实例分析
本文以实例形式讲述了C语言实现二叉树的非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如下:
先序遍历:
voidpreOrder(Node*p)//非递归 { if(!p)return; stack<Node*>s; Node*t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right)s.push(t->right); if(t->left)s.push(t->left); } }
中序遍历:
voidinOrder(Node*p) { if(!p) return; stack<pair<Node*,int>>s; Node*t; intunUsed; s.push(make_pair(p,1)); while(!s.empty()) { t=s.top().first; unUsed=s.top().second; s.pop(); if(unUsed) { if(t->right) s.push(make_pair(t->right,1)); s.push(make_pair(t,0)); if(t->left) s.push(make_pair(t->left,1)); } elseprintf("%d\n",t->data); } }
后序遍历:
voidpostOrder(Node*p) { if(!p)return; stack<pair<Node*,int>>s; Node*t; intunUsed; s.push(make_pair(p,1)); while(!s.empty()) { t=s.top().first; unUsed=s.top().second; s.pop(); if(unUsed) { s.push(make_pair(t,0); if(t->right) s.push(make_pair(t->right,1)); if(t->left) s.push(make_pair(t->left,1)); } elseprintf("%d\n",t->data); } }
希望本文所述对大家C程序算法设计的学习有所帮助。