Javascript中的樹(shù)結(jié)構(gòu)

_Dreams 發(fā)布于2019-08-23 18:10 / 853人閱讀

摘要：前沿前端中設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的方面不多，最常用的就是對(duì)樹(shù)結(jié)構(gòu)的一些操作。畢竟，就是天然的樹(shù)結(jié)構(gòu)。遞歸輸出非遞歸輸出業(yè)務(wù)場(chǎng)景前端中的樹(shù)操作，經(jīng)常是生成特定的樹(shù)結(jié)構(gòu)。

前沿

????前端中設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的方面不多，最常用的就是對(duì)樹(shù)結(jié)構(gòu)的一些操作。從某種意義上來(lái)說(shuō)，前端工作本身就是和樹(shù)結(jié)構(gòu)打交道的一個(gè)工作方向。畢竟，DOM就是天然的樹(shù)結(jié)構(gòu)。所以如何能夠良好地對(duì)樹(shù)結(jié)構(gòu)進(jìn)行操作，是前端工程師不可或缺的一項(xiàng)能力。

樹(shù)結(jié)構(gòu) 定義

????什么是樹(shù)結(jié)構(gòu)呢？從數(shù)據(jù)結(jié)構(gòu)的角度來(lái)講：

樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)
每個(gè)節(jié)點(diǎn)可能會(huì)有0個(gè)或多個(gè)后代
每個(gè)節(jié)點(diǎn)具備唯一的父節(jié)點(diǎn)（如果有多個(gè)父節(jié)點(diǎn)，那就是圖了）

分類

樹(shù)根據(jù)節(jié)點(diǎn)的不同可以分為不同的類型，最常見(jiàn)的分類是：

二叉樹(shù)

二叉搜索樹(shù)

平衡二叉查找樹(shù)

紅黑樹(shù)

具體他們之間的區(qū)別這里就不細(xì)說(shuō)了，具體請(qǐng)查看詳情

前端中常見(jiàn)的樹(shù)結(jié)構(gòu) DOM樹(shù)結(jié)構(gòu)

下面的html結(jié)構(gòu)就是一個(gè)天然的樹(shù)結(jié)構(gòu)。每個(gè)Dom節(jié)點(diǎn)下面，有0/1/多個(gè)子節(jié)點(diǎn)。

對(duì)象樹(shù)結(jié)構(gòu)

數(shù)組形式

特點(diǎn): 每一個(gè)對(duì)象節(jié)點(diǎn)，下面可能會(huì)有children，也可能沒(méi)有children

let obj = [
    {
        id: 1,
        type: "dom",
        children: [
            {
                id: 2,
                type: "html"
            }
        ]
    },
    {
        id: 3,
        type: "css",
        children: [
            {
                id: 4,
                type: "javascript"
            }
        ]
    }
];

對(duì)象形式

最常見(jiàn)的就是抽象語(yǔ)法樹(shù)：

特點(diǎn): 對(duì)象的屬性下面有不同的屬性，每一個(gè)屬性下面可能還會(huì)有不同的屬性

這種格式經(jīng)常在數(shù)據(jù)統(tǒng)計(jì)中出現(xiàn)。

Javascript中樹(shù)結(jié)構(gòu)的遍歷

????其實(shí)在我看來(lái)，樹(shù)的結(jié)構(gòu)形式有很多種，但是，前端工作中很少涉及對(duì)樹(shù)節(jié)點(diǎn)的修改等操作，大部分是遍歷和統(tǒng)計(jì)數(shù)據(jù)。

需求場(chǎng)景：下面以Dom樹(shù)結(jié)構(gòu)為例：  
1、需要輸出每個(gè)節(jié)點(diǎn)的名稱和節(jié)點(diǎn)深度  
3、深度優(yōu)先和廣度優(yōu)先都需要實(shí)現(xiàn)

假定已經(jīng)有了對(duì)應(yīng)的樹(shù)結(jié)構(gòu)，子節(jié)點(diǎn)是childNodes（為啥不用children呢？自己去查吧）

深度優(yōu)先遍歷

深度優(yōu)先遍歷，又叫DFS（deep first search），遍歷順序是優(yōu)先遍歷節(jié)點(diǎn)的子節(jié)點(diǎn)，然后再是節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

遞歸輸出

function DeepSearch(node, deep = 0) {
    const child = node.childNodes;

    const { nodeName } = node;
    console.log(`name:${nodeName},deep:${deep}`);

    for(let i = 0, len = child.length; i < len; i++) {
        DeepSearch(child[i], deep + 1);        
    }
}

非遞歸輸出

function deepSearch(node, deep = 0) {
    const stack = [];
    const deepArr = [];
    stack.push(node);
    deepArr.push(0);
    while(stack.length !== 0){
        const node = stack.shift();
        const deep = deepArr.shift();

        const { nodeName } = node;
        console.log(`name:${nodeName},deep:${deep}`);

        const nodes = child.childNodes;
        for( let i = node.length; i > 0; i--) {
            stack.unshift(nodes[i]);
            deep.unshift(deep + 1);
        }
    }
}

廣度優(yōu)先遍歷

廣度優(yōu)先，正好和深度優(yōu)先策略相反，先遍歷節(jié)點(diǎn)的兄弟節(jié)點(diǎn)，再遍歷子節(jié)點(diǎn)。

遞歸輸出

function BreadSearch(node, deep = 0) {
    const child = node.childNodes;
    const res = [];

    for(let i = 0, len = child.length; i < len; i++) {

        const { nodeName } = node;
        console.log(`name:${nodeName},deep:${deep}`);

        res.push(child[i]);
    }

    DeepSearch(res, deep + 1);        

}

非遞歸輸出

function breadSearch(node, deep = 0) {
    const stack = [];
    const deepArr = [];
    stack.push(node);
    deepArr.push(0);
    while (stack.length !== 0 ) {
        const node = stack.shift();
        cosnt deep = stack.shift();
        const { nodeName } = node;
        console.log(`name:${nodeName},deep:${deep}`);

        for(let i = 0, len = child.length; i < len; i++) {
            stack.push(child[i]);
        }
    }
}

業(yè)務(wù)場(chǎng)景

前端中的樹(shù)操作，經(jīng)常是生成特定的樹(shù)結(jié)構(gòu)。常見(jiàn)的場(chǎng)景有生成路由和生成菜單。

路由

下面以react-router為例，說(shuō)明：

簡(jiǎn)單情況（bad）

一般情況下，react-router的路由是下面的:


    
    
    
    ... ...

但是如果所有的都按照上面的寫(xiě)法，每加一個(gè)路由，都需要取在內(nèi)容下面，加一個(gè)

這樣會(huì)造成代碼不容易維護(hù)，而且可讀性不好。

配置的方式（better）

配置的方式總好過(guò)，每次打開(kāi)路由的內(nèi)部代碼修改。

const routers = [
    {
        path: "/a",
        component: A
    },
    {
        title: "考試",
        id: "exam",
        path: "/b",
        children: [
            {
                path: "/c",
                component: C
            },
            {
                path: "/d",
                component: D
            }
        ]
    }
];

function getRoute (routes, rootPath = "") {
    let res = [];
    for (let i = 0, len = routes.length; i < len; i++) {
        const route = routes[i];
        const { path } = route;
        if (route.children) {
            res = [...res, ...getRoute(route.children, path)];
        } else {
            res.push(
                
            );
        }
    }
    return res;
};


    {
        getRoute(routers)
    }

菜單

菜單和路由的方式很相似，而且通常會(huì)結(jié)合在一起使用，具體的寫(xiě)法，這里就不贅述了，因?yàn)閷?shí)在是太相似了，留給你們吧。。

參考資料

GPU云服務(wù)器云服務(wù)器 java中的樹(shù)結(jié)構(gòu)圖數(shù)據(jù)倉(cāng)庫(kù)中的邏輯結(jié)構(gòu) javascript中的 linux內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/104770.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

_Dreams

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

最強(qiáng)函數(shù)學(xué)習(xí)之路

閱讀 3479·2021-11-12 10:36
python綜合程序設(shè)計(jì)——做一個(gè)可視化大屏

閱讀 2827·2021-11-11 16:55
爆肝1萬(wàn)字《c++入門綜合》

閱讀 3053·2021-09-27 13:36
HostYun：18元/月/1GB內(nèi)存/10GB SSD空間/300GB流量/50Mbps-100M

閱讀 1679·2021-08-05 10:01
【前端詞典】滾動(dòng)穿透問(wèn)題的解決方案

閱讀 3633·2019-08-30 15:55
CSS魔法堂：重拾Border之——不僅僅是圓角

閱讀 842·2019-08-30 13:01
外邊距合并

閱讀 1965·2019-08-29 17:16
瀏覽器內(nèi)核之 CSS 解釋器和樣式布局

閱讀 2429·2019-08-29 16:40

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

Javascript中的樹(shù)結(jié)構(gòu)

相關(guān)文章

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 非線性表中的樹(shù)、堆是干嘛用的？其數(shù)據(jù)結(jié)構(gòu)是怎樣的？

**學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(四)——樹(shù)**

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 樹(shù)**

學(xué)習(xí)Virtual Dom筆記

深度剖析：如何實(shí)現(xiàn)一個(gè) Virtual DOM 算法

發(fā)表評(píng)論

0條評(píng)論

_Dreams

男|高級(jí)講師

TA的文章

最強(qiáng)函數(shù)學(xué)習(xí)之路

python綜合程序設(shè)計(jì)——做一個(gè)可視化大屏

爆肝1萬(wàn)字《c++入門綜合》

HostYun：18元/月/1GB內(nèi)存/10GB SSD空間/300GB流量/50Mbps-100M

【前端詞典】滾動(dòng)穿透問(wèn)題的解決方案

CSS魔法堂：重拾Border之——不僅僅是圓角

外邊距合并

瀏覽器內(nèi)核之 CSS 解釋器和樣式布局

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

Javascript中的樹(shù)結(jié)構(gòu)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！