今天要講的內容跟昨天很類似，一樣是要遍歷一棵樹。

再次召喚樹樹～

不過這次我們是用另外一個東西，這個叫做BFS 廣度優先搜尋。

具體來說，我們把每一個結點丟進一個queue裡面，然後一個個拿出來看出來。

import java.util.Queue
import java.util.LinkedList

class Node{
    var data:Int = 0
    var son:LinkedList<Node> = LinkedList<Node>()
    fun addSon(new_son_data:Int){
        var new_son = Node()
        new_son.data = new_son_data
        son.add(new_son)
    }
}

class Tree{
    var root = Node()
}

fun dfs(now:Node){
    print(" ${now.data} ")
    if (now.son.size!=0){
        print("{")
    }
    for(i in 0 .. now.son.size-1){
        dfs(now.son[i])
    }
    if (now.son.size!=0){
        print("} ")
    }
}

fun main(){
    var tree = Tree()
    tree.root.data = 1
    tree.root.addSon(2)
    tree.root.addSon(3)
    tree.root.son[0].addSon(4)
    tree.root.son[0].addSon(5)
    tree.root.son[0].son[1].addSon(6)
    tree.root.son[0].son[1].addSon(7)
    tree.root.son[0].son[1].addSon(8)

    var q: Queue<Node> = LinkedList<Node>()

    q.add(tree.root)
    while(!q.isEmpty()){
        var now = q.peek()
        print("${now.data} ")
        for(i in 0 .. now.son.size-1){
            q.add(now.son[i])
        }
        q.remove()
    }
}

輸出結果如下：

1 2 3 4 5 6 7 8