今天我們的目標是解決 樹狀搜尋問題

假設一個樹狀資料結構如下，該如何根據任意 id，找到這個 id 對應的文字內容呢 ?

const tree = {
    id:"a",
    text: "Today i don't feel like doing anything",
    children: [
        {
            id:"a1",
            text: "I just wanna lay in my bed",
            children: [
                 {
                    id:"a11",
                    text: "Don't feel like picking up my phone",
                    children: []
                },
            ]
        },
        {
            id:"a2",
            text: "So leave a message at the tone",
            children: []
        },
        {
            id:"a3",
            text: "Cus today I swear I'm not doing anything",
            children: []
        },
    ]
}

程序式程式設計

這個實在是跟結構化有點像，我們就默默變成五邊型吧

結構化程式設計

結構化程式設計和資料結構肯定息息相關
以這題來說可以選用 stack 做深度優先，也可以用 queue 做廣度優先
下面就先用 queue 做廣度優先，實作如下

function getNameById(target:string){
    
    let queue = [tree] // 初始化 queue
    while(queue.length > 0){
        let node = queue[0] // 處理最前面的點
        if(node.id === target){
            return node.text // 如果是目標點就結束並返回
        }
        for(let child of node.children){ // 不是目標點的話，把 children 塞進去
            queue.push(child)
        }
        queue.shift() // 第一個點處理完畢，處理下一個
    }
    return undefined
}

getNameById("all") //執行

物件導向

再說一次 XD
物件導向就是把流程(方法)和資料(屬性)打包起來

class Tree {
    root: object
    constructor (root:object) {
        this.root = root
    }
    getNameById(target:string){
        let queue = [tree]
        while(queue.length > 0){
            let node = queue[0]
            if(node.id === target){
                return node.text
            }
            for(let child of node.children){
                queue.push(child)
            }
            queue.shift()
        }
        return undefined
    }
}

const myTree = new Tree(tree) // 實體化
myTree.getNameById("a11") // 執行

函數式

函數式非常注重型別，所以我們要先定義一個 Tree 介面
然後利用 js 自帶的 map / find 這些工具函式把組合一下

interface Tree {
    id: string,
    text: string,
    children: readonly Tree []
}

const getNameById = (target:string)=>(tree:Tree):string | undefined =>
    tree.id === target 
        ? tree.text // 找到，回傳 text
        : tree.children
            // - 往下層遞迴
            // - 省略 tree 的呼叫 .map(tree => getNameById(target)(tree))
            .map(getNameById(target)) 
            // - 從 list 中找不是 undefined 的 text
            // - 如果找不到，find function 也剛好會回傳 undefined
            .find(text=>text!==undefined) 
            
getNameById("a11")(tree) // 執行

明天會對以上範例進行更詳細的說明~