js樹演算法

⑴ js廣度遍歷生成樹,樹的定義

先序，後序，中序針對二叉樹。
深度、廣度針對普通樹。深度遍歷：從樹根開始掃描，頂層掃描完了，從一層最左（也可以右）面的結點往下層掃描，直到下層已無結點，這時所有靠最左（右）的結點全部掃描完畢，從樹梢往上退一層，看這層旁有無兄弟結點，有的話還是一樣從最左（右）邊開始掃描，這是個遞歸概念，利用這一方法來遍歷整棵樹。廣度遍歷：從樹根開始掃描，頂層掃描完了，掃描一層的所有結點，掃描二層的所有結點，，掃描最底層的結點。

⑵ JS常見排序演算法

排序演算法說明:

（1）對於評述演算法優劣術語的說明

穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；

不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；

內排序 ：所有排序操作都在內存中完成；

外排序 ：由於數據太大，因此把數據放在磁碟中，而排序通過磁碟和內存的數據傳輸才能進行；

時間復雜度 : 一個演算法執行所耗費的時間。

空間復雜度 : 運行完一個程序所需內存的大小。

(2)排序演算法圖片總結:

1.冒泡排序:

解析：1.比較相鄰的兩個元素，如果前一個比後一個大，則交換位置。

2.第一輪的時候最後一個元素應該是最大的一個。

3.按照步驟一的方法進行相鄰兩個元素的比較，這個時候由於最後一個元素已經是最大的了，所以最後一個元素不用比較。

2.快速排序:

解析：快速排序是對冒泡排序的一種改進，第一趟排序時將數據分成兩部分，一部分比另一部分的所有數據都要小。然後遞歸調用，在兩邊都實行快速排序。

3.插入排序:

解析：

 （1） 從第一個元素開始，該元素可以認為已經被排序

 （2） 取出下一個元素，在已經排序的元素序列中從後向前掃描

 （3） 如果該元素（已排序）大於新元素，將該元素移到下一位置

 （4） 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

 （5）將新元素插入到下一位置中

 （6） 重復步驟2

2.二分查找:

解析：二分查找，也為折半查找。首先要找到一個中間值，通過與中間值比較，大的放又，小的放在左邊。再在兩邊中尋找中間值，持續以上操作，直到找到所在位置為止。

（1）遞歸方法

（2）非遞歸方法

4.選擇排序:

解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。

以此類推，直到所有元素均排序完畢。

5.希爾排序:

解析:先將整個待排序的記錄序列分割成為若乾子序列分別進行直接插入排序

6.歸並排序:

解析:歸並排序是一種穩定的排序方法。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

7.堆排序:

解析:堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是

小於（或者大於）它的父節點。

8.計數排序:

 解析:計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。

9.桶排序:

解析:假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排

10.基數排序:

解析:基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優

先級排序。最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以是穩定的。

基數排序 vs 計數排序 vs 桶排序

這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

基數排序：根據鍵值的每位數字來分配桶 計數排序：每個桶只存儲單一鍵值 桶排序：每個桶存儲一定范圍的數值

⑶ js中平級數組和樹形結構數據相互轉換

在實際的工作和業務需求中，我們經常會碰到樹形數據結構，比如公司組織架構、組織層級、省市縣或者事物的分類等等數據。那麼在javaScript中如何將數組轉為樹形結構和樹形結構轉為數組，本文就詳細的來探究一下。

先來看看給出了一組怎樣的數據，轉換為怎樣的樹形結構。

後台介面返回或者面試官給你的數據：

期望的處理後的數據：

如果後台給了一個這樣的數據說讓前端自己去轉換為樹形結構或者面試官給你一組這樣的數據讓你手寫一個轉換方法，你會怎麼處理？

1、遞歸實現

2、Map對象實現

3、filter實現

這種方法很有意思，可能大多數人想不到，也是從大佬處學到的(讀書人的是怎麼能叫抄呢，應該叫「竊」）。

1、rece取樹行數據的所有子集

2、遞歸實現

3、廣度優先遍歷法

⑷ JS怎樣取到樹形數據每一條的最後一層中的某個值生成新的數組

數組.Length:數組內組的個數 數組下標是從0開始，數組[0]是第一個數 所以最後一個數就是:數組[數組.Length-1]

⑸ 求大神指點js生成樹結構

// 生成樹結構
function tree(list) {
const result = [];
for (let value of list) {
// 排除空字元串的情況
if (!value) {
continue;
}
const values = value.split('/');
// 查找樹結構的當前級別是否已經存在，不存在則創建對象，並添加入列表。
let current = result.find(item => item.name === values[0]);
if (current === void 0) {
current = {};
result.push(current);
}
for (let i = 0, length = values.length; i < length; i++) {
current.name = values[i];
if (i < length - 1) {
// 如果還有下一級內容，判斷當前是否有 children，沒有則構建.
if (current.children === void 0) {
current.children = [];
}
// 查找下一級對象，為下一遍遍歷構建對象
let nextCurrent = current.children.find(item => item.name === values[i + 1]);
if (nextCurrent === void 0) {
nextCurrent = {};
current.children.push(nextCurrent);
}
current = nextCurrent;
}
}
}
return result;
}
============ 假裝分割線 ===========
以上代碼是生成樹的函數，調用 tree 函數並傳入你的 input 數據，返回值就是生成的樹。網路沒找到傳代碼的地方了。

⑹ JS樹結構數據的遍歷

title: JS樹結構數據的遍歷
date: 2022-04-14
description: 針對項目中出現樹形結構數據的時候，我們怎樣去操作他

項目中我們會經常出現對樹形結構的遍歷、查找和轉換的場景，比如說DOM樹、族譜、社會機構、組織架構、許可權、菜單、省市區、路由、標簽等等。那針對這些場景和數據，我們又如何去遍歷和操作，有什麼方式或者技巧可以簡化我們的實現思路。下面我們將針對常規出現的場景去總結一下我們的遍歷方式

樹的特點
1、每個節點都只有有限個子節點或無子節點；
2、沒有父節點的節點稱為根節點；
3、每一個非根節點有且只有一個父節點；
4、除了根節點外，每個子節點可以分為多個不相交的子樹；
5、樹裡面沒有環路

下面的圖片表示一顆樹

在下面的JS中我們由多棵樹組成我們的數據

在這數據中我們如何評判數據是否為葉節點（也就是最後一級），我們每個節點都會存在children屬性，如果不存在children屬性或者children不是一個數組或者children為數組且長度為0我們則認為他是一個葉節點

我們針對樹結構的操作離不開遍歷，遍歷的話又分為廣度優先遍歷、深度優先遍歷。其中深度優先遍歷可以通過遞歸和循環的方式實現，而廣度優先遍歷的話是非遞歸的

從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。即訪問樹結構的第n+1層前必須先訪問完第n層。

簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。

所以我們的實現思路是，維護一個隊列，隊列的初始值為樹結構根節點組成的列表，重復執行以下步驟直到隊列為空：
取出隊列中的第一個元素，進行訪問相關操作，然後將其後代元素（如果有）全部追加到隊列最後。

深度優先搜索演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜索樹或圖的演算法。這個演算法會盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止

1、先序遍歷
訪問子樹的時候，先訪問根再訪問根的子樹

2、後序遍歷
訪問子樹的時候，先訪問子樹再訪問根

1、先序遍歷
先序遍歷與廣度優先循環實現類似，要維護一個隊列，不同的是子節點不追加到隊列最後，而是加到隊列最前面

2、後序遍歷
後序遍歷就略微復雜一點，我們需要不斷將子樹擴展到根節點前面去，執行列表遍歷，並且通過一個臨時對象維護一個id列表，當遍歷到某個節點如果它沒有子節點或者它本身已經存在於我們的臨時id列表，則執行訪問操作，否則繼續擴展子節點到當前節點前面

對於樹結構的遍歷操作，其實遞歸是最基礎，也是最容易理解的。遞歸本身就是循環的思想，所以可以用循環來改寫遞歸,以上的方式在項目中已經廊括了大部分的場景了，我們在日常開發中可以根據場景或者需要去選擇我們的遍歷方式，或者基於此對他進行調整和優化，至於每種方式的空間復雜度和時間復雜度我們在這個地方就不去嘗試了，各位感興趣可以自己去驗證。

廣度優先搜索

樹的遍歷

深度優先搜索

圖文詳解兩種演算法：深度優先遍歷（DFS）和廣度優先遍歷（BFS）

二叉樹遍歷（前序，後序，中序，層次）遞歸與迭代實現JavaScript

JS樹結構操作:查找、遍歷、篩選、樹和列表相互轉換

⑺ js的樹形結構怎麼實現

這個問題，我建議你去下載下樹形菜單。網上已經實現的js很多，下載下來一看就明白了，

⑻ JS中的各種排序方法

數據結構演算法中排序有很多種，常見的、不常見的，至少包含十種以上。根據它們的特性，可以大致分為兩種類型：比較類排序和非比較類排序

冒泡排序是一次比較兩個元素，如果順序是錯誤的就把它們交換過來。，直到不需要再交換

快速排序的基本思想是通過一趟排序，將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可以分別對這兩部分記錄繼續進行排序，以達到整個序列有序

從數列中挑出一個元素，稱為 「基準」（pivot）；然後重新排序數列，所有元素比基準值小的擺放在基準前面、比基準值大的擺在基準的後面；在這個區分搞定之後，該基準就處於數列的中間位置；然後把小於基準值元素的子數列（left）和大於基準值元素的子數列（right）遞歸地調用 quick 方法排序完成，這就是快排的思路

通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入，從而達到排序的效果

插入排序的思路是基於數組本身進行調整的，首先循環遍歷從 i 等於 1 開始，拿到當前的 current 的值，去和前面的值比較，如果前面的大於當前的值，就把前面的值和當前的那個值進行交換，通過這樣不斷循環達到了排序的目的

將最小的元素存放在序列的起始位置，再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序的序列後面……以此類推，直到所有元素均排序完畢

堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質，即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆的底層實際上就是一棵完全二叉樹，可以用數組實現

歸並排序是建立在歸並操作上的一種有效的排序演算法，該演算法是採用分治法的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並

通過 mid 可以把該數組分成左右兩個數組，分別對這兩個進行遞歸調用排序方法，最後將兩個數組按照順序歸並起來

⑼ 求最簡單的方法進行原生js 循環遍歷樹(json數據)

遞歸吧般樹都遞歸

⑽ javascript如何用遞歸寫一個簡單的樹形結構

vartree=[
{name:'node1'},
{name:'node2',children:[{name:'node-2-1'},{name:'node2-2'}]},
{name:'node3',children:[{name:'node-3-1',children:[{name:'node3-1-1'}]},{name:'node3-2'}]}
];

varrender=functionrender(tree){
if(!tree)returnnull

varul=document.createElement('ul');
tree.forEach(({name,children})=>{
varli=document.createElement('li')
varlabel=document.createElement('span');label.innerText=name;
li.appendChild(label);
varsub=render(children);
sub&&li.appendChild(sub);
ul.append(li);
})
returnul
};

document.body.innerHTML='';
document.body.appendChild(render(tree));