树和森林的遍历相关总结

树和森林都有两种遍历方法，分别为先序遍历和后序遍历。但对于森林的后序遍历，有的教材叫中序遍历，其实它们是同一种遍历方法，只是叫法不同。而二叉树的遍历方式有先序遍历，中序遍历，后序遍历和层次遍历。树或森林转化为二叉树后，树或森林的先序遍历对应二叉树的先序遍历，树或森林的后序遍历对应二叉树的中序遍历。

⑴树的三种存储方式：双亲表示法、孩子链表表示法、孩子-兄弟存储方表示法

①双亲表示法（一般按层序存储，实际是一个静态链表）

②孩子链表表示法(与图的邻接表极为相似)

③孩子-兄弟存储方表示法

⑵二叉树的深度优先遍历和广度优先遍历，分别相当于二叉树按照先序遍历和层次遍历的方法进行遍历。

①二叉树层次遍历算法

void level(BTnode *p)

{

int font,rear;

 BTnode *que[maxSize];

front=rear=0;

BTnode *q;

 if(p!=NULL)

 {

 rear=(rear+1)%maxSize;

 que[rear]=p;

 while(front !=rear)

 {

 front=(front+1)%maxSize;

 q=que[front];

 Visit(q);

 if(q->lchild !=NULL)

 {

 rear=(rear+1)%maxSize;

 que[rear]=q->lchild;

 }

 if(q->rchild!=NULL)

{

 rear=(rear+1)%maxSize;

 que[rear]=q->rchild;

}

 }

}

}

②二叉树中序遍历算法

void inorderNonrecursion(BTnode *bt)

{

 if(bt !=NNLL)

{

BTNode *stack[maxSize];int top=-1;

BTNode *p;

p=bt;

while(top !=-1||p !=NULL)

 {

while(top !=NULL)

 {

Stack[++top]=p;

p=p->lchild;

 }

if(rop !=-1)

 {

 p=stack[top–];

Visit(p);

 p=p->rchild;

}

 }

 }

}