树和森林的遍历及存储方式

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

一、树的三种存储方式

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

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

(3)孩子-兄弟存储方表示法

二、二叉树的深度优先遍历和广度优先遍历

分别相当于二叉树按照先序遍历和层次遍历的方法进行遍历

三、算法代码

(1)二叉树层次遍历算法
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;}}}}
(2)二叉树中序遍历算法
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;}}}}