義
樹是一種數據結構,由一組表示分層樹結構的鏈接節點組成。每個節點都通過父子關系鏈接到其他節點。樹中的第一個節點是根,而沒有任何子節點的節點是葉子。
JavaScript 樹可視化
樹數據結構中的每個節點都必須具有以下屬性:
key: 節點的鍵
value: 節點的值
parent: 節點的父節點(null如果沒有)
children: 指向節點子節點的指針數組
樹形數據結構的主要操作有:
insert: 插入一個節點作為給定父節點的子節點
remove: 從樹中刪除一個節點及其子節點
find: 檢索給定節點
preOrderTraversal: 通過遞歸遍歷每個節點及其子節點來遍歷樹
postOrderTraversal: 通過遞歸遍歷每個節點的子節點來遍歷樹
class TreeNode {
constructor(key, value=key, parent=null) {
this.key=key;
this.value=value;
this.parent=parent;
this.children=[];
}
get isLeaf() {
return this.children.length===0;
}
get hasChildren() {
return !this.isLeaf;
}
}
class Tree {
constructor(key, value=key) {
this.root=new TreeNode(key, value);
}
*preOrderTraversal(node=this.root) {
yield node;
if (node.children.length) {
for (let child of node.children) {
yield* this.preOrderTraversal(child);
}
}
}
*postOrderTraversal(node=this.root) {
if (node.children.length) {
for (let child of node.children) {
yield* this.postOrderTraversal(child);
}
}
yield node;
}
insert(parentNodeKey, key, value=key) {
for (let node of this.preOrderTraversal()) {
if (node.key===parentNodeKey) {
node.children.push(new TreeNode(key, value, node));
return true;
}
}
return false;
}
remove(key) {
for (let node of this.preOrderTraversal()) {
const filtered=node.children.filter(c=> c.key !==key);
if (filtered.length !==node.children.length) {
node.children=filtered;
return true;
}
}
return false;
}
find(key) {
for (let node of this.preOrderTraversal()) {
if (node.key===key) return node;
}
return undefined;
}
}
用class創建一個類TreeNode,使用構造函數初始化 key, value, parent 和 children。
定義一個isLeaf getter方法,用Array.prototype.length檢查children是否為空。
定義一個hasChildren getter方法,用來檢查是否有子節點。
用 class 創建一個Tree,使用構造函數初始化樹的根節點。
定義一個preOrderTraversal() 方法,按順序遍歷樹的生成器方法,使用 yield* 語法將遍歷委托給自身。
定義一個postOrderTraversal()方法,以后序遍歷樹的生成器方法,使用yield*語法將遍歷委托給自身。
定義一個insert()方法,使用preOrderTraversal()和Array.prototype.push()方法向樹中添加一個TreeNode 節點。
定義一個remove()方法,使用preOrderTraversal()和Array.prototype.filter()方法從樹刪除一個TreeNode節點。
定義一個find()方法,使用preOrderTraversal()方法檢索樹中的給定節點。
const tree=new Tree(1, 'AB');
tree.insert(1, 11, 'AC');
tree.insert(1, 12, 'BC');
tree.insert(12, 121, 'BG');
[...tree.preOrderTraversal()].map(x=> x.value);
// ['AB', 'AC', 'BC', 'BCG']
tree.root.value; // 'AB'
tree.root.hasChildren; // true
tree.find(12).isLeaf; // false
tree.find(121).isLeaf; // true
tree.find(121).parent.value; // 'BC'
tree.remove(12);
[...tree.postOrderTraversal()].map(x=> x.value);
// ['AC', 'AB']
eb瀏覽器創建Document對象,并且開始解析Web頁面,解析HTML元素和它們的文本內容后添加Element對象和Text節點到文檔中.在這個階段document.readystate屬性的值是”loading”.
當HTML解析器遇到沒有async和defer屬性的<script>元素時,它把這些元素添加到文檔中,然后執行行內或外部腳本.這些腳本會同步執行,并且在腳本下載(如果需要)和執行時解析器會暫停.這樣腳本就可以用document.write()來把文本插入到輸入流中.解析器恢復時這些文本會成為文檔的一部分.同步腳本經常簡單定義函數和注冊后面使用的注冊事件處理程序,但它們可以遍歷和操作文檔樹,因為在它們執行時已經存在了.這樣,同步腳本可以看到它自己的<script>元素和它們之前的文檔內容.
當解析器遇到設置了async屬性的<script>元素時,它開始下載腳本文本,并繼續解析文檔.腳本會在它下載完成后盡快執行,但是解析器沒有停下來等它下載.異步腳本禁止使用document.write()方法.它們可以看到自己的<script>元素和它之前的所有文檔元素,并且可能或干脆不可能訪問其他的文檔內容.
當文檔完成解析,document.readyState屬性變成“interactive”.
所有有defer屬性的腳本,會按它們在文檔的里的出現順序執行.異步腳本可能也會在這個時間執行.延遲腳本能訪問完整的文檔樹,禁止使用document.write()方法.
瀏覽器在Document對象上觸發DOMContentLoaded事件.這標志著程序執行從同步腳本執行階段轉換到了異步事件驅動階段.但要注意,這時可能還有異步腳本沒有執行完成.
這時,文檔已經完全解析完成,但是瀏覽器可能還在等待其他內容載入,如圖片.當所有這些內容完成載入時,并且所有異步腳本完成載入和執行,document.readyState屬性改變為“complete”,Web瀏覽器觸發Window對象上的load事件.
從此刻起,會調用異步事件,以異步響應用戶輸入事件、網絡事件、計時器過期等.
David Flanagan. JavaScript權威指南
JavaScript時間線
原文:https://os-note.com/articles/client-side-javascript-timeline.html
產品說要讓前端用 JavaScript 畫一棵樹出來,但是這難道不能直接讓 UI 給一張圖片嗎?
后來一問才知道,產品要的是一顆 隨機樹,也就是樹的茂盛程度、長度、枝干粗細都是隨機的,那這確實沒辦法叫 UI 給圖,畢竟 UI 不可能給我 10000 張樹的圖片吧?
所以第一時間想到的就是 Canvas,用它來畫這棵隨機樹(文末有完整代碼)
接下來使用 Canvas 去畫這棵隨機樹
基礎頁面
我們需要在頁面上寫一個 canvas 標簽,并設置好寬高,同時需要獲取它的 Dom 節點、繪制上下文,以便后續的繪制
坐標調整
默認的 Canvas 坐標系是這樣的
但是我們現在需要從中間去向上去畫一棵樹,所以坐標得調整成這樣:
這些操作可以使用 Canvas 的方法
繪制一棵樹的要素
繪制一棵樹的要素是什么呢?其實就是樹枝和果實,但是其實樹枝才是第一要素,那么樹枝又有哪些要素呢?無非就這幾個點
開始繪制
所以我們可以寫一個 drawBranch 來進行繪制,并且初始調用肯定是繪制樹干,樹干的參數如下:
這個終點應該怎么算呢?其實很簡單,根據樹枝長度、生長角度就可以算出來了,這是初高中的知識
于是我們可以使用 Canvas 的繪制方法,去繪制線段,其實樹枝就是一個一個的線段
到現在我繪制出了一個樹干 出來
但是我們是想讓這棵樹開枝散葉,所以需要繼續遞歸繼續去繪制更多的樹枝出來~
遞歸繪制
其實往哪開枝散葉呢?無非就是往左或者往右
所以需要遞歸畫左邊和右邊的樹枝,并且子樹枝肯定要比父樹枝更短、比父樹枝更細,比如我們可以定義一個比例
而子樹枝的生長角度,其實可以隨機,我們可以在 0° - 30° 之間隨機選一個角度,于是增加了遞歸調用的代碼
但是這個時候會發現,報錯了,爆棧了,因為我們只遞歸開始,但卻沒有在某個時刻遞歸停止
我們可以自己定義一個停止規則(規則可以自己定義,這會決定你這棵樹的茂盛程度):
現在可以看到我們已經大致繪制出一棵樹了
不過還少了樹的果實
繪制果實
繪制果實很簡單,只需要在繪制樹枝結束的時候,去把果實繪制出來就行,其實果實就是一個個的白色實心圓
至此這棵樹完整繪制完畢
繪制部分的代碼如下
*請認真填寫需求信息,我們會在24小時內與您取得聯系。