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

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

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

前沿

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

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

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

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

分類

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

二叉樹

二叉搜索樹

平衡二叉查找樹

紅黑樹

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

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

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

對象樹結(jié)構(gòu)

數(shù)組形式

特點: 每一個對象節(jié)點，下面可能會有children，也可能沒有children

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

對象形式

最常見的就是抽象語法樹：

特點: 對象的屬性下面有不同的屬性，每一個屬性下面可能還會有不同的屬性

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

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

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

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

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

深度優(yōu)先遍歷

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

遞歸輸出

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é)點的兄弟節(jié)點，再遍歷子節(jié)點。

遞歸輸出

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ù)場景

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

路由

下面以react-router為例，說明：

簡單情況（bad）

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


    
    
    
    ... ...

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

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

配置的方式（better）

配置的方式總好過，每次打開路由的內(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)
    }

菜單

菜單和路由的方式很相似，而且通常會結(jié)合在一起使用，具體的寫法，這里就不贅述了，因為實在是太相似了，留給你們吧。。

參考資料