二叉树的遍历算法(详细示例分析)

voidprint(intv)
{
   cout<<v<<"  ";
}
voidPreOrderTraverse(Node*n,void(*visit)(int))
{
   assert(n!=NULL&&visit!=NULL);
   (*visit)(n->v);
   if(n->leftChild!=NULL)PreOrderTraverse(n->leftChild,visit);
   if(n->rightChild!=NULL)PreOrderTraverse(n->rightChild,visit);
}

voidInOrderTraverse(Node*n,void(*visit)(int))
{
   assert(n!=NULL&&visit!=NULL);
   if(n->leftChild!=NULL)InOrderTraverse(n->leftChild,visit);
   (*visit)(n->v);
   if(n->rightChild!=NULL)InOrderTraverse(n->rightChild,visit);
}

voidPostOrderTraverse(Node*n,void(*visit)(int))
{
   assert(n!=NULL&&visit!=NULL);
   if(n->leftChild!=NULL)PostOrderTraverse(n->leftChild,visit);
   if(n->rightChild!=NULL)PostOrderTraverse(n->rightChild,visit);
   (*visit)(n->v);
}
//非递归版本，将递归改成非递归一般都要利用一个栈
//每次访问一个结点后，在向左子树遍历下去之前，利用这个栈记录该结点的右子女（如果有的话）结点的地址，
//以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续右子树的遍历
voidPreOrder(Node*n,void(*visit)(int))
{
   stack<Node*>sta;
   sta.push(n);
   while(!sta.empty())
   {
       Node*t=sta.top();
       sta.pop();
       assert(t!=NULL);
       (*visit)(t->v);
       if(t->rightChild!=NULL)sta.push(t->rightChild);
       if(t->leftChild!=NULL)sta.push(t->leftChild);
   }
}

//非递归中序遍历
voidInOrder(Node*n,void(*visit)(int))
{
   stack<Node*>sta;
   sta.push(n);
   Node*p=n;
   while(!sta.empty()&&p!=NULL)
   {
       p=sta.top();
       while(p!=NULL&&!sta.empty())
       {
           sta.push(p->leftChild);
           p=p->leftChild;
       }
       sta.pop();//弹出空指针
       if(!sta.empty())
       {
           p=sta.top();
           sta.pop();
           (*visit)(p->v);
           sta.push(p->rightChild);
       }
   }
}

//非递归后续遍历

structStkNode
{
   Node*ptr;
   booltag;//false=leftandtrue=right
   StkNode():ptr(NULL),tag(false)
   {}
};
voidPostOrder(Node*n,void(*visit)(int))
{
   stack<StkNode>sta;
   StkNodew;
   Node*p=n;
   do{
       while(p!=NULL)
       {
           w.ptr=p;
           w.tag=false;
           sta.push(w);
           p=p->leftChild;
       }
       boolflag=true;
       while(flag&&!sta.empty())
       {
           w=sta.top();
           sta.pop();
           p=w.ptr;
           if(!w.tag)//left,如果从左子树返回，则开始遍历右子树
           {
               w.tag=true;//标记右子树
               sta.push(w);
               flag=false;
               p=p->rightChild;
           }
           else
           {
               (*visit)(p->v);
           }
       }
   }while(!sta.empty());
}

//层序遍历，利用队列
voidLevelOrderTraverse(Node*n,void(*visit)(int))
{
   assert(n!=NULL&&visit!=NULL);
   queue<Node*>que;
   que.push(n);
   while(!que.empty())
   {
       Node*t=que.front();
       (*visit)(t->v);
       que.pop();
       if(t->leftChild!=NULL)que.push(t->leftChild);
       if(t->rightChild!=NULL)que.push(t->rightChild);
   }
}

intmain()
{
   Node*head=newNode(0);
   Node*node1=newNode(1);
   Node*node2=newNode(2);
   Node*node3=newNode(3);
   Node*node4=newNode(4);
   Node*node5=newNode(5);
   Node*node6=newNode(6);

   head->leftChild=node1;
   head->rightChild=node2;   
   node1->leftChild=node3;
   node1->rightChild=node4;
   node2->rightChild=node5;
   node4->leftChild=node6;

   
/*   LevelOrderTraverse(head,print);
   cout<<endl;
   PreOrderTraverse(head,print);
   cout<<endl;*/
   InOrder(head,print);
   cout<<endl;
   InOrderTraverse(head,print);
   cout<<endl;

   PostOrder(head,print);
   cout<<endl;
   PostOrderTraverse(head,print);
   cout<<endl;
   return0;
}