在应用树结构解决问题时，往往要求按照某种此项获得树中全部结点的信息，这种操作叫做树的遍历。遍历的方法有很多种。常用的有：

A. 先序遍历：先访问根结点，再从左到右按照先序思想遍历各子树。

B. 后序遍历：先从左到右遍历各个子树，再访问根结点。

C.层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。

D.叶结点遍历：有时把所有的数据信息都存放叶结点中，而其余结点都是用来表示数据之间的某种分支或层次关系，这种情况就用这种方法。

A,B用的思想就是我们常说的“深度优先遍历”

void tral(tree t,int m)  {      if(t)      {          cout<<t->data<<endl;          for(int i=0;i<m;i++){              tral(t->child[i],m);          }      }    }

C方法实际上就是我们常说的“广度优先搜索”思想如下：若某个结点别访问，则该结点的子结点应记录，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点，为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下：

const int n=100;  int head,tail,i;  tree q[n];  tree p;  void work()  {      tail=head=1;      q[tail]=t;      tail++; //队尾为空      while(head<tail){          p=q[head]          head++;          cout<<p->data<<" ";          for(i=0;i<m;i++)          if(p->child[d])          {              q[tail]=p—>child[i];              tail++;          }      }  }

(adsbygoogle = window.adsbygoogle || []).push({});