一、树的遍历
1.先根遍历(根左右)——深度优先遍历
若树非空,先访问根节点,再依次对每棵子树进行先根遍历
//树的先根遍历
void PreOrder(TreeNode *R){
if(R!=NULL){
visit(R); //访问根结点
while(R还有下一棵子树T)
PreOrder(T); //先根遍历下一棵子树
}
}
【注意】树的**先根遍历序列 与 这棵树相应二叉树的先序序列**相同
2.后根遍历(左右根)——深度优先遍历
若树非空,先依次对每棵子树进行后根遍历,最后在访问根节点
//树的后根遍历
void PostOrder(TreeNode *R){
if(R!=NULL){
while(R还有下一棵子树T)
PostOrder(T); //后根遍历
visit(R); //访问根结点
}
}
【注意】树的**后根遍历序列 与 这棵树相应二叉树的中序序列**相同
3.层序遍历(用队列来实现)——广度优先遍历
①若树非空,则根节点入队
②对队列非空,队头元素出队并访问,同时将该元素的孩子依次入队
③重复②直至队列为空
二、森林的遍历
1.先序遍历
若森林为非空,则按照如下规则进行遍历:
①访问森林中第一棵树的根结点
②先序遍历第一棵树中的根结点的子树森林
③先序遍历除去第一棵树之后剩余的树构成的森林
【此过程的效果等同于**依次对各个树进行先根遍历**】
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)