搜尋
首頁web前端js教程詳細介紹JavaScript二元樹及各種遍歷演算法

本篇文章為大家帶來了關於javascript的相關知識,主要介紹了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
*/

廣度優先遍歷

實作想法如下:

    #建立佇列,把根節點入隊
  • 把對頭出隊並訪問
  • 把隊頭的
  • leftright依序入隊
  • #重複執行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中文網其他相關文章!

陳述
本文轉載於:脚本之家。如有侵權,請聯絡admin@php.cn刪除
JavaScript是用C編寫的嗎?檢查證據JavaScript是用C編寫的嗎?檢查證據Apr 25, 2025 am 12:15 AM

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

JavaScript的角色:使網絡交互和動態JavaScript的角色:使網絡交互和動態Apr 24, 2025 am 12:12 AM

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

C和JavaScript:連接解釋C和JavaScript:連接解釋Apr 23, 2025 am 12:07 AM

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

從網站到應用程序:JavaScript的不同應用從網站到應用程序:JavaScript的不同應用Apr 22, 2025 am 12:02 AM

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

Python vs. JavaScript:比較用例和應用程序Python vs. JavaScript:比較用例和應用程序Apr 21, 2025 am 12:01 AM

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

C/C在JavaScript口譯員和編譯器中的作用C/C在JavaScript口譯員和編譯器中的作用Apr 20, 2025 am 12:01 AM

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

JavaScript在行動中:現實世界中的示例和項目JavaScript在行動中:現實世界中的示例和項目Apr 19, 2025 am 12:13 AM

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

JavaScript和Web:核心功能和用例JavaScript和Web:核心功能和用例Apr 18, 2025 am 12:19 AM

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

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

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

熱工具

Safe Exam Browser

Safe Exam Browser

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

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

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

MantisBT

MantisBT

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

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器