本篇文章為大家帶來了關於javascript的相關知識,主要介紹了JavaScript二元樹及各種遍歷演算法詳情,文章圍繞主題展開詳細的內容介紹,具有一定的參考價值,需要的小夥伴可以參考一下,希望對大家有幫助。
【相關推薦:javascript影片教學、web前端】
什麼是二元樹
二元樹是每個節點最多只能有兩個子節點的樹,如下圖所示:
一個二元樹具有以下幾個特質:
- 第
i
層的節點最有隻有2^(i-1)
個; - 如果這顆二元樹的深度為
k
,那二元樹最多有2^k-1
節點; - 在一個非空的二元樹中,若使用
n0
表示葉子節點的個數,n2
是度為2的非葉子節點的個數,那麼兩者滿足關係n0 = n2 1
。
滿二叉樹
如果在一個二元樹中,除了葉子節點,其餘的節點的每個度數都是2,則說明該二元樹是一個滿二叉樹,
如下圖所示:
#滿叉樹除了滿足普通二元樹特質,還具有如下幾個特質:
- 滿二元樹的第
n
層具有2^(n-1)
個節點; - 深度為
k
的滿二叉樹一定存在2^k-1
個節點,葉子節點的個數為2^(k-1)
; - 具有
n
個節點的滿二元樹的深度為log_2^(n 1)
。
完全二元樹
如果一個二元樹去掉最後一次層是滿二叉樹,且最後一次的節點是依序從左到右分佈的,則這個二元樹是一個完全二元樹,
如下圖所示:
#二元樹的儲存
儲存二元樹的常見方式分為兩種,一種是使用陣列儲存,另一種使用鍊錶儲存。
陣列儲存
使用陣列儲存二元樹,如果遇到完全二元樹,儲存順序從上到下,從左到右,如下圖所示:
如果是非完全二元樹,如下圖所示:
需要先將其轉換為完全二元樹,然後在進行存儲,如下圖所示:
#可以很明顯的看到存儲空間的浪費。
鍊錶儲存
使用鍊錶儲存通常將二元樹中的分為3個部分,如下圖:
##這三個部分依序是左子樹的引用,該節點包含的數據,右子樹的引用,儲存方式如下圖所示:
以下演算法中遍歷用到的樹如下:
// tree.js const bt = { val: 'A', left: { val: 'B', left: { val: 'D', left: null, right: null }, right: { val: 'E', left: null, right: null }, }, right: { val: 'C', left: { val: 'F', left: { val: 'H', left: null, right: null }, right: { val: 'I', left: null, right: null }, }, right: { val: 'G', left: null, right: null }, }, } module.exports = bt深度優先遍歷
二元樹的深度優先遍歷與樹的深度優先遍歷思路一致,思路如下:
- #訪問根節點;
- 訪問根節點的
- left
- right
實作程式碼如下: #
const bt = { val: 'A', left: { val: 'B', left: { val: 'D', left: null, right: null }, right: { val: 'E', left: null, right: null }, }, right: { val: 'C', left: { val: 'F', left: { val: 'H', left: null, right: null }, right: { val: 'I', left: null, right: null }, }, right: { val: 'G', left: null, right: null }, }, } function dfs(root) { if (!root) return console.log(root.val) root.left && dfs(root.left) root.right && dfs(root.right) } dfs(bt) /** 结果 A B D E C F H I G */廣度優先遍歷
實作想法如下:
- #建立佇列,把根節點入隊
- 把對頭出隊並訪問
- 把隊頭的
- left
和
right依序入隊
#重複執行2、3步,直到隊列為空
實作程式碼如下:
function bfs(root) { if (!root) return const queue = [root] while (queue.length) { const node = queue.shift() console.log(node.val) node.left && queue.push(node.left) node.right && queue.push(node.right) } } bfs(bt) /** 结果 A B C D E F G H I */先序遍歷
二元樹的先序遍歷實作想法如下: #
- 访问根节点;
- 对当前节点的左子树进行先序遍历;
- 对当前节点的右子树进行先序遍历;
如下图所示:
递归方式实现如下:
const bt = require('./tree') function preorder(root) { if (!root) return console.log(root.val) preorder(root.left) preorder(root.right) } preorder(bt) /** 结果 A B D E C F H I G */
迭代方式实现如下:
// 非递归版 function preorder(root) { if (!root) return // 定义一个栈,用于存储数据 const stack = [root] while (stack.length) { const node = stack.pop() console.log(node.val) /* 由于栈存在先入后出的特性,所以需要先入右子树才能保证先出左子树 */ node.right && stack.push(node.right) node.left && stack.push(node.left) } } preorder(bt) /** 结果 A B D E C F H I G */
中序遍历
二叉树的中序遍历实现思想如下:
- 对当前节点的左子树进行中序遍历;
- 访问根节点;
- 对当前节点的右子树进行中序遍历;
如下图所示:
递归方式实现如下:
const bt = require('./tree') // 递归版 function inorder(root) { if (!root) return inorder(root.left) console.log(root.val) inorder(root.right) } inorder(bt) /** 结果 D B E A H F I C G */
迭代方式实现如下:
// 非递归版 function inorder(root) { if (!root) return const stack = [] // 定义一个指针 let p = root // 如果栈中有数据或者p不是null,则继续遍历 while (stack.length || p) { // 如果p存在则一致将p入栈并移动指针 while (p) { // 将 p 入栈,并以移动指针 stack.push(p) p = p.left } const node = stack.pop() console.log(node.val) p = node.right } } inorder(bt) /** 结果 D B E A H F I C G */
后序遍历
二叉树的后序遍历实现思想如下:
- 对当前节点的左子树进行后序遍历;
- 对当前节点的右子树进行后序遍历;
- 访问根节点;
如下图所示:
递归方式实现如下:
const bt = require('./tree') // 递归版 function postorder(root) { if (!root) return postorder(root.left) postorder(root.right) console.log(root.val) } postorder(bt) /** 结果 D E B H I F G C A */
迭代方式实现如下:
// 非递归版 function postorder(root) { if (!root) return const outputStack = [] const stack = [root] while (stack.length) { const node = stack.pop() outputStack.push(node) // 这里先入left需要保证left后出,在stack中后出,就是在outputStack栈中先出 node.left && stack.push(node.left) node.right && stack.push(node.right) } while (outputStack.length) { const node = outputStack.pop() console.log(node.val) } } postorder(bt) /** 结果 D E B H I F G C A */
【相关推荐:javascript视频教程、web前端】
以上是詳細介紹JavaScript二元樹及各種遍歷演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

是的,JavaScript的引擎核心是用C語言編寫的。 1)C語言提供了高效性能和底層控制,適合JavaScript引擎的開發。 2)以V8引擎為例,其核心用C 編寫,結合了C的效率和麵向對象特性。 3)JavaScript引擎的工作原理包括解析、編譯和執行,C語言在這些過程中發揮關鍵作用。

JavaScript是現代網站的核心,因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容,2)通過DOMAPI操作網頁,3)支持複雜的交互效果如動畫和拖放,4)優化性能和最佳實踐提高用戶體驗。

C 和JavaScript通過WebAssembly實現互操作性。 1)C 代碼編譯成WebAssembly模塊,引入到JavaScript環境中,增強計算能力。 2)在遊戲開發中,C 處理物理引擎和圖形渲染,JavaScript負責遊戲邏輯和用戶界面。

JavaScript在網站、移動應用、桌面應用和服務器端編程中均有廣泛應用。 1)在網站開發中,JavaScript與HTML、CSS一起操作DOM,實現動態效果,並支持如jQuery、React等框架。 2)通過ReactNative和Ionic,JavaScript用於開發跨平台移動應用。 3)Electron框架使JavaScript能構建桌面應用。 4)Node.js讓JavaScript在服務器端運行,支持高並發請求。

Python更適合數據科學和自動化,JavaScript更適合前端和全棧開發。 1.Python在數據科學和機器學習中表現出色,使用NumPy、Pandas等庫進行數據處理和建模。 2.Python在自動化和腳本編寫方面簡潔高效。 3.JavaScript在前端開發中不可或缺,用於構建動態網頁和單頁面應用。 4.JavaScript通過Node.js在後端開發中發揮作用,支持全棧開發。

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。1)C 用于解析JavaScript源码并生成抽象语法树。2)C 负责生成和执行字节码。3)C 实现JIT编译器,在运行时优化和编译热点代码,显著提高JavaScript的执行效率。

JavaScript在現實世界中的應用包括前端和後端開發。 1)通過構建TODO列表應用展示前端應用,涉及DOM操作和事件處理。 2)通過Node.js和Express構建RESTfulAPI展示後端應用。

JavaScript在Web開發中的主要用途包括客戶端交互、表單驗證和異步通信。 1)通過DOM操作實現動態內容更新和用戶交互;2)在用戶提交數據前進行客戶端驗證,提高用戶體驗;3)通過AJAX技術實現與服務器的無刷新通信。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

Safe Exam Browser
Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

VSCode Windows 64位元 下載
微軟推出的免費、功能強大的一款IDE編輯器