您好,登錄后才能下訂單哦!
這篇文章主要講解了“JavaScript樹結(jié)構(gòu)深度優(yōu)先算法怎么使用”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“JavaScript樹結(jié)構(gòu)深度優(yōu)先算法怎么使用”吧!
在現(xiàn)實(shí)生活中,相信每個人對樹都很熟悉,不管是柳樹、楊樹還是桃樹,可以說樹在我們生活中隨處可見;在計(jì)算機(jī)世界,樹是一種分層結(jié)構(gòu)的抽象模型,
如下圖所示:
樹結(jié)構(gòu)的應(yīng)用有很多,就比如公司的組織架構(gòu),就可以用樹來表示,如下圖:
除了組織架構(gòu),像族譜、省市等都可以使用樹結(jié)構(gòu)來表示。
樹有很多的術(shù)語,如下圖:
樹:n(n≥0)個節(jié)點(diǎn)所構(gòu)成的有限集合,當(dāng)n=0
時,稱為空樹;
節(jié)點(diǎn)的度:節(jié)點(diǎn)的子樹個數(shù),例如B節(jié)點(diǎn)的度就是2,A節(jié)點(diǎn)的度就是3;
樹的度:樹的所有節(jié)點(diǎn)中最大的度數(shù),例如上圖中,樹的度是3;
葉子節(jié)點(diǎn):度為0的節(jié)點(diǎn),也叫葉節(jié)點(diǎn);
子節(jié)點(diǎn):如上圖;
兄弟節(jié)點(diǎn):如上圖;
根節(jié)點(diǎn):如上圖;
樹的深度:樹中所有結(jié)點(diǎn)中的最大層次,例如上圖中樹的深度就是3;
節(jié)點(diǎn)的層次:例如E節(jié)點(diǎn)的層次就是3,節(jié)點(diǎn)的層次就是父節(jié)點(diǎn)層次+1,根節(jié)點(diǎn)的層次為1;
路徑:一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)的通道,例如A→H的路徑就是A D H
;
路徑長度:一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)的距離,例如A→H的路徑就是3。
樹結(jié)構(gòu)可以說是前端中最常見的數(shù)據(jù)結(jié)構(gòu)之一,比如說DOM樹、級聯(lián)選擇、樹形組件等等;
JavaScript中并沒有提供樹這個數(shù)據(jù)結(jié)構(gòu),但是我們可以通過對象和數(shù)組來模擬一個樹,
例如下面這段代碼:
const tree = { value: 'A', children: [ { value: 'B', children: [ { value: 'E', children: null }, { value: 'F', children: null }, ], }, { value: 'C', children: [{ value: 'G', children: null }], }, { value: 'D', children: [ { value: 'H', children: null }, { value: 'I', children: null }, ], }, ], }
所謂的深度優(yōu)先遍歷算法,就是盡可能深的去搜索樹的分支,它的遍歷順序如下圖:
實(shí)現(xiàn)思路如下:
訪問根節(jié)點(diǎn);
對根節(jié)點(diǎn)的children
持續(xù)進(jìn)行深度優(yōu)先遍歷(遞歸);
實(shí)現(xiàn)代碼如下:
function dfs(root) { console.log(root.value) root.children && root.children.forEach(dfs) // 與下面一致 // if (root.children) { // root.children.forEach(child => { // dfs(child) // }) // } } dfs(tree) // 這個tree就是前面定義的那個樹 /* 結(jié)果 A B E F C G D H I */
可以看到,和圖中的順序是一致的,也就是說我們的算法沒有問題。
所謂的廣度優(yōu)先就是依次訪問離根節(jié)點(diǎn)近的節(jié)點(diǎn),它的遍歷順序如下圖:
實(shí)現(xiàn)思路如下:
創(chuàng)建要給隊(duì)列,把根節(jié)點(diǎn)入隊(duì);
把隊(duì)頭出隊(duì)并訪問;
把隊(duì)頭的children
依次入隊(duì);
重復(fù)執(zhí)行2、3步,直到隊(duì)列為空。
實(shí)現(xiàn)代碼如下:
function bfs(root) { // 1. 新建隊(duì)列 跟節(jié)點(diǎn)入隊(duì) const q = [root] // 4 重復(fù)執(zhí)行 while (q.length > 0) { const node = q.shift() // 2 隊(duì)頭出隊(duì) console.log(node.value) // 3 隊(duì)頭 children 依次入隊(duì) node.children && node.children.forEach(child => { q.push(child) }) } } bfs(tree) /* 結(jié)果 A B C D E F G H I */
可以看到,和圖中的順序是一致的,也就是說我們的算法沒有問題。
感謝各位的閱讀,以上就是“JavaScript樹結(jié)構(gòu)深度優(yōu)先算法怎么使用”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對JavaScript樹結(jié)構(gòu)深度優(yōu)先算法怎么使用這一問題有了更深刻的體會,具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。