C语言二叉树的非递归遍历实例分析

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如下：

先序遍历：

void preOrder(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);
 }
}

中序遍历：

void inOrder(Node *p)
{
if(!p)
return;
stack< pair<Node*,int> > s;
Node *t;
int unUsed;
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));
}
else printf("％d\n",t->data);
}
}

后序遍历：

void postOrder(Node *p)
{
 if(!p) return;
 stack<pair<Node*,int> > s;
 Node *t;
 int unUsed;
 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));
   }
   else printf("％d\n",t->data);
 }
}

希望本文所述对大家C程序算法设计的学习有所帮助。