Csharp/C#教程：二叉树的遍历算法(详细示例分析)分享

代码如下:
#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>
usingnamespacestd;
structNode
{
   intv;
   Node*leftChild,*rightChild;
   Node():leftChild(NULL),rightChild(NULL){}
   Node(intvv):leftChild(NULL),rightChild(NULL)
   {
       v=vv;
   }
};

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;
}

您可能感兴趣的文章:平衡二叉树的实现实例二叉树的非递归后序遍历算法实例详解二叉树先序遍历的非递归算法具体实现二叉树先根（先序）遍历的改进c语言版本二叉树基本操作示例(先序递归非递归)python二叉树遍历的实现方法python二叉树的实现实例C++二叉树结构的建立与基本操作二叉树遍历非递归C++实现代码先序遍历二叉树的递归实现与非递归实现深入解析PHPClass&Object–解析PHP实现二叉树PHPClass&Object–PHP自排序二叉树的深入解析如何在二叉树中找出和为某一值的所有路径探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)深入理解二叉树的非递归遍历深入遍历二叉树的各种操作详解（非递归遍历）深入二叉树两个结点的最低共同父结点的详解平衡二叉树AVL操作模板

C++实现位图排序实例

基于C++实现的各种内部排序算法汇总

上述就是C#学习教程：二叉树的遍历算法(详细示例分析)分享的全部内容，如果对大家有所用处且需要了解更多关于C#学习教程，希望大家多多关注—计算机技术网(www.ctvol.com)!