使用遞歸遍歷并轉換樹形數據（以TypeScript為例）

作者：邊城 2017-11-02 14:46:18

樹形數據的遍歷有兩種方法，大家都知道：廣度遍歷和深度遍歷。一般情況下，廣度遍歷是采用隊列來實現，而深度遍歷剛更適合使用遞歸來實現。

一個朋友問我應該怎么從一個樹的 JSON 數組生成 HTML，使用 <ul> 和 <li> 來構建頁面元素。于是我簡單的畫了個樹型結構圖

然后寫了對應的模擬數據(JavaScript 對象)

const data = { 
    name: "A", 
    nodes: [ 
        { name: "B", nodes: [{ name: "F" }] }, 
        { name: "C" }, 
        { 
            name: "D", 
            nodes: [ 
                { name: "G" }, 
                { name: "H" }, 
                { name: "I", nodes: [{ name: "J" }, { name: "K" }] } 
            ] 
        }, 
        { name: "E" } 
    ] 
};

***寫了一個遞歸，生成了 HTML 的樹型結構。原本是用 JavaScript ES6 寫的，為了表明數據結構，這里改用 TypeScript 來寫：

interface INode { 
    name: string; 
    nodes?: INode[]; 
} 
 
function makeTree(roots: INode[]): JQuery<HTMLElement> { 
    function makeNode(node: INode): JQuery<HTMLElement> { 
        const $div = $("<div>").text(node.name || ""); 
        const $li = $("<li>").append($div); 
        if (node.nodes && node.nodes.length) { 
            $li.append(makeNodeList(node.nodes)); 
        } 
        return $li; 
    } 
 
    function makeNodeList(nodes: INode[]): JQuery<HTMLElement> { 
        return nodes 
            .map(child => makeNode(child)) 
            .reduce(($ul, $li) => { 
                return $ul.append($li); 
            }, $("<ul>")); 
    } 
 
    return makeNodeList(roots); 
}

效果還是蠻不錯的

看看源碼(轉譯成 JS 之后的)：http://jsfiddle.net/y7bw4yj2/

然后朋友說沒看明白，好吧，那我從頭講起

遍歷方法

樹形數據的遍歷有兩種方法，大家都知道：廣度遍歷和深度遍歷。一般情況下，廣度遍歷是采用隊列來實現，而深度遍歷剛更適合使用遞歸來實現。

廣度遍歷

從圖上大致可以理解廣度遍歷的過程：

準備一個空隊列;
將根(單根或多根均可)節點放到隊列中;
從隊列中取出一個節點
處理(比如打印)這個節點
檢查節點的子節點，如果有，全部依次添加到隊列中
回到第 3 步開始處理，直到隊列為空(處理完成)

function travelWidely(roots: INode[]) { 
    const queue: INode[] = [...roots]; 
    while (queue.length) { 
        const node = queue.shift()!; 
        // 打印節點名稱及其子節點數 
        console.log(`${node.name} ${node.nodes && node.nodes.length || ""}`); 
        if (node.nodes && node.nodes.length) { 
            queue.push(...node.nodes); 
        } 
    } 
} 
 
// 開始遍歷 
travelWidely([data]);

const node = queue.shift()!，這后面的 ! 后綴表示聲明其結果不為 undefined 或 null。這是一個 TypeScript 語法。由于 .shift() 在數組中沒有元素時會返回 undefined，所以其返回類型被聲明為 INode | undefined，由于從邏輯可以保證 .shift() 一定會返回一個節點對象，所以這里用 ! 后綴忽略類型中的 undefined 部分，使 node 的類型被推導為 INode。

代碼里稍難理解一點的是要注意 queue 的內容和長度隨時在變化。如果想使用 for 代替 while 循環，節點序號會因 .shift() 而不斷變化，所以 i < queue.length 這樣的判斷是錯誤的。

深度遍歷

深度遍歷是一個遞歸過程，遞歸一直是編程的難點。

遞歸是一個循環往復的處理過程，它有兩個點需要注意：

遞歸調用點，遞歸調用自己(或另一個可能會調用自己的函數)
遞歸結束點，退出當前函數

以樹節點為例，我們期望處理過程是處理(打印)一個樹結點，即 printNode(node: INode)。那么它的

遞歸調用點：如果該節點有子節點，依次對子節點調用 printNode(children[i])
遞歸結束點：處理完所有子節點(子節點數量是有限的，所以一定會結束)

用一段偽代碼描述這一過程

function printNode(node: INode) { 
    // 處理該節點 
    console.log(node.name); 
     
    // 遞歸調用點：循環對子節點調用 printNode 
    node.nodes!.forEach(child => printNode(child)); 
     
    // 遞歸結束點：循環完成，return 
}

上面兩句代碼就完成了遞歸過程，但實際上情況還要復雜些，因為要處理入口和容錯。

// 注意參數支持傳入單根或多根， 
// 如果像 travelWidely 那樣只支持多根（單根是特例）也是可以的 
function travelDeeply(roots: INode | INode[]) { 
    function printNode(node: INode) { 
        console.log(`${node.name} ${node.nodes && node.nodes.length || ""}`); 
        if (node.nodes && node.nodes.length) { 
            // 依次對子節點遞歸調用 printNode 
            node.nodes.forEach(child => printNode(child)); 
        } 
    } 
 
    // 這里 printNode 和 node => printNode(node) 等價 
    (Array.isArray(roots) ? roots : [roots]).forEach(printNode); 
} 
 
// 開始遍歷 
travelDeeply(data);

關于遞歸，我正好在慕課網上講生成數據解決方案的時候講到了，有興趣可以看看。

遍歷還沒講完

上面兩種遍歷都講到了，但是還沒講完——因為兩種遍歷都是以打印為例，而我們的目的是要生成 DOM 樹。生成 DOM 樹與純打印信息的不同之處在于，我們不僅要使用節點信息，還要從節點信息生成 DOM 返回出來。

深度遍歷生成節點

這次先講深度遍歷，因為遞歸更容易實現。遞歸本身具有層次信息，每進入一個遞歸調用點，就會深入一層，每離開一個遞歸結束點，就會減少一層。所以這個算法本身能夠保留結構信息，相應代碼也會更容易實現。而且在本文一開始，就已經實現出來了。

需要注意的一點是那段代碼用了兩個函數來完成遞歸過程：

makeNode 處理單個節點，它調用 makeNodeList 處理子節點列表
makeNodeList 遍歷節點列表，分別對其調用 makeNode 來進行處理

makeNode 和 makeNodeList 的相互調用形成了遞歸，上述兩條都是遞歸調用點，而遞歸結束點同樣也有兩條：

makeNode 處理的節點沒有子節點時，不會調用 makeNodeList
makeNodeList 中的循環結束時，不會再調用 makeNode

廣度遍歷生成節點

廣度遍歷的過程是把所有節點扁平化到一個隊列中了，這個過程是不可逆的，換句話說，我們在處理過程中丟掉了樹形結構信息。然后我們要生成的 DOM 樹，是需要結構信息的——因此，需要將結構信息附加在每個節點上。這里我們把生成的 DOM 和數據節點綁定起來，由 DOM 保存結構信息。為此，需要修改一下節點類型

interface INode { 
    name: string; 
    nodes?: INode[]; 
    dom: JQuery;    // 附加生成的 DOM 
}

function makeTreeWidely(roots: INode[]): JQuery { 
    // 從一組節點生成 <ul>，為每個節點生成并附加 <li>， 
    // 同時將 <li> 到到 <ul> 中保存結構信息 
    function makeUl(nodes: INode[]) { 
        return nodes 
            .map(node => { 
                const $li = $("<li>") 
                    .append($("<div>").text(node.name || "")); 
                node.dom = $li; 
                return $li; 
            }) 
            .reduce(($ul, $li) => $ul.append($li), $("<ul>")); 
    } 
 
    const $rootUl = makeUl(roots); 
 
    const queue: INode[] = [...roots]; 
    while (queue.length) { 
        const node = queue.shift()!; 
 
        if (node.nodes && node.nodes.length) { 
            const $ul = makeUl(node.nodes); 
            node.dom.append($ul); 
            queue.push(...node.nodes); 
        } 
    } 
    return $rootUl; 
}

雖然這里和上面講遞歸遍歷 printNode 的時候一樣定義了局部函數表達式 makeUl，但這里沒有遞歸，因為 makeUl 內部沒有調用自身，或者某個會調用 makeUl 的函數。

但問題還是再深入一點，因為上面的代碼改變了原數據。而一般情況下，我們應該盡量避免這樣的副作用

沒有副作用的廣度遍歷生成節點

// 聲明一個新結構，它把 INode 和 DOM 組合在一起。 
// 這個結構將代替 INode 作為隊列的元素類型 
interface IDomNode { 
    node: INode; 
    dom: JQuery; 
} 
 
function makeTreeWidely(roots: INode[]): JQuery { 
    // convert 將節點數組轉換為 IDomNode 數組， 
    // 同時還干了原來 makeUl 干的事情，返回一個 $ul 
    function convert(nodes: INode[]) { 
        const domNodes = nodes 
            .map(node => { 
                const $li = $("<li>") 
                    .append($("<div>").text(node.name || "")); 
                return { 
                    node, 
                    dom: $li 
                }; 
            }); 
 
        const $ul = domNodes 
            .reduce(($ul, dn) => $ul.append(dn.dom), $("<ul>")); 
 
        // 將兩個數組組成一個元組（對象）返回 
        return { 
            domNodes, 
            $ul 
        }; 
    } 
 
    // 解析元組，聲明變量 queue 和 $rootUl， 
    // 并分別將 domNodes 和 $ul 的值賦值給 queue 和 $rootUl 兩個變量 
    const { domNodes: queue, $ul: $rootUl } = convert(roots); 
 
    while (queue.length) { 
        const { node, dom } = queue.shift()!; 
 
        if (node.nodes && node.nodes.length) { 
            const { domNodes, $ul } = convert(node.nodes); 
            dom.append($ul); 
            queue.push(...domNodes); 
        } 
    } 
    return $rootUl; 
}  
看療效：http://jsfiddle.net/y7bw4yj2/1/

責任編輯：龐桂玉來源： segmentfault