Javascript中的樹結構

_Dreams 發布于2019-08-23 18:10 / 792人閱讀

摘要：前沿前端中設計數據結構的方面不多，最常用的就是對樹結構的一些操作。畢竟，就是天然的樹結構。遞歸輸出非遞歸輸出業務場景前端中的樹操作，經常是生成特定的樹結構。

前沿

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

樹結構 定義

????什么是樹結構呢？從數據結構的角度來講：

樹是非線性數據結構

每個節點可能會有0個或多個后代

每個節點具備唯一的父節點（如果有多個父節點，那就是圖了）

分類

樹根據節點的不同可以分為不同的類型，最常見的分類是：

二叉樹

二叉搜索樹

平衡二叉查找樹

紅黑樹

具體他們之間的區別這里就不細說了，具體請查看詳情

前端中常見的樹結構 DOM樹結構

下面的html結構就是一個天然的樹結構。每個Dom節點下面，有0/1/多個子節點。

對象樹結構

數組形式

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

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

對象形式

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

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

這種格式經常在數據統計中出現。

Javascript中樹結構的遍歷

????其實在我看來，樹的結構形式有很多種，但是，前端工作中很少涉及對樹節點的修改等操作，大部分是遍歷和統計數據。

需求場景：下面以Dom樹結構為例：  
1、需要輸出每個節點的名稱和節點深度  
3、深度優先和廣度優先都需要實現

假定已經有了對應的樹結構，子節點是childNodes（為啥不用children呢？自己去查吧）

深度優先遍歷

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

遞歸輸出

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);
        }
    }
}

廣度優先遍歷

廣度優先，正好和深度優先策略相反，先遍歷節點的兄弟節點，再遍歷子節點。

遞歸輸出

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]);
        }
    }
}

業務場景

前端中的樹操作，經常是生成特定的樹結構。常見的場景有生成路由和生成菜單。

路由

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

簡單情況（bad）

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


    
    
    
    ... ...

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

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

配置的方式（better）

配置的方式總好過，每次打開路由的內部代碼修改。

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)
    }

菜單

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

參考資料

GPU云服務器云服務器 java中的樹結構圖數據倉庫中的邏輯結構 javascript中的 linux內核中的數據結構

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/104770.html

JavaScript 數據結構與算法之美 - 非線性表中的樹、堆是干嘛用的？其數據結構是怎樣的？

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。非線性表中的樹堆是干嘛用的其數據結構是怎樣的希望大家帶著這兩個問題閱讀下文。其中，前中后序，表示的是節點與它的左右子樹節點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想學好前端，先練好內功，內功不行，...

singerye 2019-08-26 10:09 評論0 收藏0
學習javascript數據結構(四)——樹

摘要：原文博客地址學習數據結構四樹知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人之所能，不能兼備，棄其所短，取其所長。通常子樹被稱作左子樹和右子樹。敬請期待數據結構篇最后一篇文章學習數據結構五圖參考文章樹數據結構二叉樹前言總括：本文講解了數據結構中的[樹]的概念，盡可能通俗易懂的解釋樹這種數據結構的概念，使用javascript實現了樹，如有紕漏，歡迎批評指正。 ...

Dean 2019-08-20 13:47 評論0 收藏0
學習JavaScript數據結構與算法 — 樹

摘要：定義樹同散列表一樣，是一種非順序數據結構。一個節點及其后代可以組成一個子樹如圖中的。方法允許傳入子樹一直遍歷左側子節點，直到底部搜索特定值搜索特定值的處理與插入值的處理類似。同理，找左側子樹的最大值替換上來也可以。定義樹同散列表一樣，是一種非順序數據結構。現實中樹的例子有家譜、公司組織架構圖及其它樹形結構關系。樹由一系列節點構成，每個節點都有一個父節點（除根節點外）以及零個或多個子...

shiguibiao 2019-08-21 11:32 評論0 收藏0
學習Virtual Dom筆記

摘要：通過深度優先遍歷兩棵樹，每層節點進行對比，記錄下每個節點的差異。所以可以對那棵樹也進行深度優先遍歷，遍歷的時候從步驟二生成的對象中找出當前遍歷的節點差異，然后進行操作。實現虛擬(Virtual) Dom 把一個div元素的屬性打印出來，如下： showImg(https://segmentfault.com/img/bVbnPe1?w=1239&h=336); 可以看到僅僅是第一層，...

DobbyKim 2019-08-26 13:28 評論0 收藏0
深度剖析：如何實現一個 Virtual DOM 算法

摘要：本文所實現的完整代碼存放在。這就是所謂的算法。兩個樹的完全的算法是一個時間復雜度為的問題。如果有差異的話就記錄到一個對象里面。如和的不同，會被所替代。這牽涉到兩個列表的對比算法，需要另外起一個小節來討論。作者：戴嘉華轉載請注明出處并保留原文鏈接（ https://github.com/livoras/blog/issues/13 ）和作者信息。目錄： 1 前言 2 對前端應用狀...

vvpvvp 2019-08-21 10:49 評論0 收藏0