【数据结构】树与森林（二）

3）层次遍历

• 若树为非空，则从根节点开始，从上到下依次访问每一层的各个结点，在同一层中的结点，则按从左到右的顺序依次进行访问。
  

ABCDEFGHIJK

publicvoidlevelTraverse(CSTreeNodeT) {
if(T!=null) {
LinkQueueL=newLinkQueue();      //构建队列L.offer(T);                         //根节点入队列while(!L.isEmpty()) {
for(T=L.poll() ; T!=null ; T=T.nextisibling) {
System.out.print(T.data+" ");
if(T.firstChild!=null) {  //第一个孩子结点非空入队列L.offer(T.firstchild);
                }
            }
        }
    }
}

5.6.7 森林的遍历

• 森林由3部分组成：

1. 森林中第一棵树的根节点
   
2. 森林中第一棵树的子树森林
   
3. 森林中其他树构成的森林。
   

• 森林的3中遍历：

1. 先根遍历
   
2. 后根遍历
   
3. 层次遍历
   

1）先根遍历

• 若森林不空，则可依下列次序进行遍历

1. 访问森林中第一棵树的根节点
   
2. 先序遍历第一课树中的子树森林
   
3. 先序遍历除去第一棵树之后剩余的树构成的森林。
   

• 也就是说：依次从左到右对森林中的每一颗树进行先根遍历。
  

先跟遍历顺序是：

ABCEDFGHIJKL

2）后根遍历

• 若森林不空，则可依下列次序进行遍历
  

1. 后根遍历第一棵树中的子树森林
   
2. 访问森林中第一棵树的根节点
   
3. 后根遍历除去第一棵树之后剩余的树构成的森林。
   

• 也就是说：依次从左至右对森林中的每一棵树进行后根遍历。
  

后根遍历序列是：

BECDAGFIKLJH

4）层次遍历

• 若森林为非空，则按从左到右的顺序对森林中每一颗树进行层次遍历。
  
• 也就是说：依次从左至右对森林中的每一棵树进行层次遍历。
  

层次遍历序列：

ABCDEFGHIJKL

5.7 作业