如何從一個(gè)樹的 JSON 數(shù)組生成 HTML,使用 《ul》 和 《li》 來構(gòu)建頁(yè)面元素。本文就來講講這個(gè)話題。
然后寫了對(duì)應(yīng)的模擬數(shù)據(jù)(JavaScript 對(duì)象)
最后寫了一個(gè)遞歸,生成了 HTML 的樹型結(jié)構(gòu)。原本是用 JavaScript ES6 寫的,為了表明數(shù)據(jù)結(jié)構(gòu),這里改用 TypeScript 來寫:
效果還是蠻不錯(cuò)的
然后朋友說沒看明白,好吧,那我從頭講起
遍歷方法
樹形數(shù)據(jù)的遍歷有兩種方法,大家都知道:廣度遍歷和深度遍歷。一般情況下,廣度遍歷是采用隊(duì)列來實(shí)現(xiàn),而深度遍歷剛更適合使用遞歸來實(shí)現(xiàn)。
廣度遍歷
從圖上大致可以理解廣度遍歷的過程:
準(zhǔn)備一個(gè)空隊(duì)列;
將根(單根或多根均可)節(jié)點(diǎn)放到隊(duì)列中;
從隊(duì)列中取出一個(gè)節(jié)點(diǎn)
處理(比如打?。┻@個(gè)節(jié)點(diǎn)
檢查節(jié)點(diǎn)的子節(jié)點(diǎn),如果有,全部依次添加到隊(duì)列中
回到第 3 步開始處理,直到隊(duì)列為空(處理完成)
const node = queue.shift()!,這后面的 ! 后綴表示聲明其結(jié)果不為 undefined 或 null。這是一個(gè) TypeScript 語(yǔ)法。由于 .shift() 在數(shù)組中沒有元素時(shí)會(huì)返回 undefined,所以其返回類型被聲明為 INode | undefined,由于從邏輯可以保證 .shift() 一定會(huì)返回一個(gè)節(jié)點(diǎn)對(duì)象,所以這里用 ! 后綴忽略類型中的 undefined 部分,使 node 的類型被推導(dǎo)為 INode。
代碼里稍難理解一點(diǎn)的是要注意 queue 的內(nèi)容和長(zhǎng)度隨時(shí)在變化。如果想使用 for 代替 while 循環(huán),節(jié)點(diǎn)序號(hào)會(huì)因 .shift() 而不斷變化,所以 i 《 queue.length 這樣的判斷是錯(cuò)誤的。
深度遍歷
深度遍歷是一個(gè)遞歸過程,遞歸一直是編程的難點(diǎn)。
遞歸是一個(gè)循環(huán)往復(fù)的處理過程,它有兩個(gè)點(diǎn)需要注意:
遞歸調(diào)用點(diǎn),遞歸調(diào)用自己(或另一個(gè)可能會(huì)調(diào)用自己的函數(shù))
遞歸結(jié)束點(diǎn),退出當(dāng)前函數(shù)
以樹節(jié)點(diǎn)為例,我們期望處理過程是處理(打?。┮粋€(gè)樹結(jié)點(diǎn),即 printNode(node: INode)。那么它的
遞歸調(diào)用點(diǎn):如果該節(jié)點(diǎn)有子節(jié)點(diǎn),依次對(duì)子節(jié)點(diǎn)調(diào)用 printNode(children[i])
遞歸結(jié)束點(diǎn):處理完所有子節(jié)點(diǎn)(子節(jié)點(diǎn)數(shù)量是有限的,所以一定會(huì)結(jié)束)
用一段偽代碼描述這一過程
上面兩句代碼就完成了遞歸過程,但實(shí)際上情況還要復(fù)雜些,因?yàn)橐幚砣肟诤腿蒎e(cuò)。
遍歷還沒講完
上面兩種遍歷都講到了,但是還沒講完——因?yàn)閮煞N遍歷都是以打印為例,而我們的目的是要生成 DOM 樹。生成 DOM 樹與純打印信息的不同之處在于,我們不僅要使用節(jié)點(diǎn)信息,還要從節(jié)點(diǎn)信息生成 DOM 返回出來。
深度遍歷生成節(jié)點(diǎn)
這次先講深度遍歷,因?yàn)檫f歸更容易實(shí)現(xiàn)。遞歸本身具有層次信息,每進(jìn)入一個(gè)遞歸調(diào)用點(diǎn),就會(huì)深入一層,每離開一個(gè)遞歸結(jié)束點(diǎn),就會(huì)減少一層。所以這個(gè)算法本身能夠保留結(jié)構(gòu)信息,相應(yīng)代碼也會(huì)更容易實(shí)現(xiàn)。而且在本文一開始,就已經(jīng)實(shí)現(xiàn)出來了。
需要注意的一點(diǎn)是那段代碼用了兩個(gè)函數(shù)來完成遞歸過程:
makeNode 處理單個(gè)節(jié)點(diǎn),它調(diào)用 makeNodeList 處理子節(jié)點(diǎn)列表
makeNodeList 遍歷節(jié)點(diǎn)列表,分別對(duì)其調(diào)用 makeNode 來進(jìn)行處理
makeNode 和 makeNodeList 的相互調(diào)用形成了遞歸,上述兩條都是遞歸調(diào)用點(diǎn),而遞歸結(jié)束點(diǎn)同樣也有兩條:
makeNode 處理的節(jié)點(diǎn)沒有子節(jié)點(diǎn)時(shí),不會(huì)調(diào)用 makeNodeList
makeNodeList 中的循環(huán)結(jié)束時(shí),不會(huì)再調(diào)用 makeNode
廣度遍歷生成節(jié)點(diǎn)
廣度遍歷的過程是把所有節(jié)點(diǎn)扁平化到一個(gè)隊(duì)列中了,這個(gè)過程是不可逆 的,換句話說,我們?cè)谔幚磉^程中丟掉了樹形結(jié)構(gòu)信息。然后我們要生成的 DOM 樹,是需要結(jié)構(gòu)信息的——因此,需要將結(jié)構(gòu)信息附加在每個(gè)節(jié)點(diǎn)上。這里我們把生成的 DOM 和數(shù)據(jù)節(jié)點(diǎn)綁定起來,由 DOM 保存結(jié)構(gòu)信息。為此,需要修改一下節(jié)點(diǎn)類型
雖然這里和上面講遞歸遍歷 printNode 的時(shí)候一樣定義了局部函數(shù)表達(dá)式 makeUl,但這里沒有遞歸,因?yàn)?makeUl 內(nèi)部沒有調(diào)用自身,或者某個(gè)會(huì)調(diào)用 makeUl 的函數(shù)。
但問題還是再深入一點(diǎn),因?yàn)樯厦娴拇a改變了原數(shù)據(jù)。而一般情況下,我們應(yīng)該盡量避免這樣的副作用
沒有副作用的廣度遍歷生成節(jié)點(diǎn)
評(píng)論
查看更多