树和森林的遍历相关总结

  • 2017-11-07 13:10:33
  • 5,292 次阅读
  • 稿源:天马行空

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

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

①双亲表示法(一般按层序存储,实际是一个静态链表)

parent

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

firstChild

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

parentFirstChild

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

①二叉树层次遍历算法

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;

}

 }

 }

}

 

喜欢 0

文章评论 (1)

  1. 创业网说道:

    冬天虽已来临,祝您四季如春!

    [1楼]网友 Windows 7 | 搜狗浏览器 2.X   

表情

大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头