當前位置：首頁 > 前端技术 > javascript >内容正文

javascript

javascript实现二叉搜索树

發布時間：2025/4/16 javascript 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 javascript实现二叉搜索树小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

在使用javascript實現基本的數據結構中，練習了好幾周，對基本的數據結構如棧、隊列、鏈表、集合、哈希表、樹、圖等內容進行了總結并且寫了筆記和代碼。

在 github中可以看到? 點擊查看，可以關注一下我哈。

樹的基本術語

二叉樹節點的存儲結構

創建一個二叉搜索樹

二叉樹的先序、中序、后續遍歷算法

二叉樹的非遞歸先序、中序、后續遍歷算法。

文章對樹了解的不多的人有點不友好，這里簡單介紹（從書上抄下來）那些基本的一點概念吧。

看下面這個示意圖

樹的基本術語：

結點：A、B、C等都是結點，結點不僅包含數據元素，而且包含指向子樹的分支。例如，A結點不僅包含數據元素A、還包含3個指向子樹的指針。

結點的度：結點擁有的子樹個數或者分支的個數，例如A結點有3棵子樹，所以A結點的度為3.

樹的度：樹中各結點度的最大值。如例子中結點度最大為3（A、D結點）。最小為0（F、G、I、J、K、L、M），所以樹的度為3。

葉子節點：又叫做終端節點，指度為0的節點，F、G、I、J、K、L、M節點都是葉子節點。

孩子：結點的子樹的根，如A節點的孩子為B、C、D。

雙親：與孩子的定義對應，如B C D結點的雙親都是A。

兄弟：同一個雙親的孩子之間互為兄弟。如B、C、D互為兄弟，因為它們都是A節點的孩子。

祖先：從根到某節點的路徑上的所有結點，都是這個節點的祖先。如K的祖先是A B E，因為從A到K的路徑為 A---B---E--K。

子孫: 以某節點為根的子樹中的所有結點，都是該結點的子孫。如D的子孫為H I J M。

層次：從根開始，根為第一層，根的孩子為第二層，根的孩子的孩子為第三層，以此類推。

樹的高度（或者深度）：樹中結點的最大層次，如例子中的樹共有4層，所以高度為4.

理解了上面的樹一些基本一些的概念后，我們來看一下什么是二叉樹。

1）每個結點最多只有兩棵子樹，即二叉樹中的節點的度只能為0、1、2

2) 子樹有左右之分，不能顛倒。

以下二叉樹的5中基本狀態

構造一個二叉樹的節點存儲結構

我們會發現，二叉樹中的存儲結構一個是值，一個是左邊有一個，右邊有一個。他們分別叫左孩子/左子樹? 右孩子/右子樹。

所以我們會很容易的寫出來一個節點的構造函數。

1 // 樹的結構 2 class BTNode { 3 constructor() { 4 this.key = key; 5 this.lchild = null; 6 this.rchild = null; 7 } 8 }

實現一個二叉搜索樹 / 二叉排序樹

看一下定義

二叉排序樹或者是空樹，或者是滿足以下性質的二叉樹。

1) 若它的左子樹不空，則左子樹上的所有關鍵字的值均小于根關鍵字的值。

2）若它的右子樹不空，則右子樹上所有關鍵字的值均大于根關鍵字的值。

3）左右子樹又是一棵二叉排序樹。

舉個例子

假如要插入一堆數字，數字為 20 10 5 15 13 18 17 30

?那么用代碼如何實現呢？

?在瀏覽器中一層一層的展開看看是否和我們的一樣。

二叉樹的遍歷算法?

二叉樹的遍歷算法，二叉樹的遍歷就是按照某種規則將二叉樹中的所有數據都訪問一遍。

二叉樹的遍歷方式有先序遍歷、中序遍歷、后續遍歷和層次遍歷，很多算法都是基于這幾種遍歷方式衍生出來的。

遞歸方式的具體的代碼實現

1 let BST = (function () { 2 3 let ROOT = Symbol(); 4 5 // 節點結構 6 let BTNode = class { 7 constructor(key) { 8 this.key = key; 9 this.lchild = null; 10 this.rchild = null; 11 } 12 } 13 14 // 遞歸插入節點 15 let recursionInsert = function (root, node) { 16 if (node.key < root.key) { 17 if (root.lchild) { 18 recursionInsert(root.lchild, node); 19 } else { 20 root.lchild = node; 21 } 22 } else { 23 if (root.rchild) { 24 recursionInsert(root.rchild, node); 25 } else { 26 root.rchild = node; 27 } 28 } 29 }; 30 31 // 用于中序遍歷二叉樹的方法 32 let inorderTraversal = function (root, arr) { 33 if (!root) return; 34 inorderTraversal(root.lchild, arr); 35 arr.push(root.key); 36 inorderTraversal(root.rchild, arr); 37 }; 38 39 // 用于先序遍歷的遞歸函數 40 let preOrderTraversal = function (root, arr) { 41 if (!root) return; 42 arr.push(root.key); 43 preOrderTraversal(root.lchild, arr); 44 preOrderTraversal(root.rchild, arr); 45 }; 46 47 // 用于后續遍歷的遞歸函數 48 let lastOrderTraversal = function (root, arr) { 49 if (!root) return; 50 lastOrderTraversal(root.lchild, arr); 51 lastOrderTraversal(root.rchild, arr); 52 arr.push(root.key); 53 }; 54 55 // 二叉搜索樹類 56 return class { 57 constructor() { 58 this[ROOT] = null; 59 } 60 61 // 插入 62 insert(key) { 63 let node = new BTNode(key); 64 let root = this[ROOT]; 65 if (!root) { 66 this[ROOT] = node; 67 return; 68 } 69 // 遞歸插入 70 recursionInsert(root, node); 71 } 72 73 74 // 中序遍歷二叉樹 75 inorderTraversal() { 76 let arr = []; 77 inorderTraversal(this[ROOT], arr); 78 return arr; 79 } 80 81 // 先序遍歷二叉樹 82 preOrderTraversal() { 83 let arr = []; 84 preOrderTraversal(this[ROOT], arr); 85 return arr; 86 } 87 88 // 后續遍歷 89 lastOrderTraversal() { 90 let arr = []; 91 lastOrderTraversal(this[ROOT], arr); 92 return arr; 93 } 94 } 95 96 })(); 97 98 99 let bst = new BST(); 100 101 bst.insert(20); 102 bst.insert(15); 103 bst.insert(7); 104 bst.insert(40); 105 bst.insert(30); 106 bst.insert(45); 107 bst.insert(50); 108 109 110 console.log(bst); 111 112 113 let a = bst.inorderTraversal(); 114 let b = bst.preOrderTraversal(); 115 let c = bst.lastOrderTraversal(); 116 117 console.log(a); 118 console.log(b); 119 console.log(c);

廣度優先遍歷

// 廣度優先遍歷 breadthRirstSearch() {// 初始化用于廣度優先遍歷的隊列let queue = new Queue();console.log('根節點', this[ROOT]);let arr = [];let root = this[ROOT];if (!root) return;queue.enqueue(root);while (queue.size()) {let queueFirst = queue.dequeue();arr.push(queueFirst.key);queueFirst.lchild && queue.enqueue(queueFirst.lchild);queueFirst.rchild && queue.enqueue(queueFirst.rchild);}return arr; }

二叉樹遍歷算法的改進

上面介紹的二傻叔的深度優先遍歷算法都是用遞歸函數實現的，這是很低效的，原因就在于系統幫你調用了一個棧并做了諸如保護現場和恢復現場等復雜的操作，才使得遍歷可以用非常簡潔的代碼實現。

有的人可能會想到，關于二叉樹深度優先遍歷算法的非遞歸實現和遞歸實現，一個是用戶自己定義棧，一個是系統棧，為什么用戶自己定義的棧要比系統棧執行高效？
一個較為通俗的解釋是：遞歸函數所申請的系統棧，是一個所有遞歸函數都通用的棧，對于二叉樹深度優先遍歷算法，系統棧除了記錄訪問過的節點信息之外，還有其他信息需要記錄，以實現函數的遞歸調用，用戶自己定義的棧僅保存了遍歷所需的節點信息，是對遍歷算法的一個針對性的設計，對于遍歷算法來說，顯然要比遞歸函數通用的系統棧更高，也就是一般情況下，專業的要比通用的要好一些。

然而在實際應用中不是這樣的，如尾遞歸在很多機器上都會被優化為循環，因此遞歸函數不一定就比非遞歸函數執行效率低。

棧數據結構，滿足后進先出的規則用來輔佐我們遍歷

// 棧結構用來輔助非遞歸遍歷 class Stack {constructor() {this.items = [];}push(data) {this.items.push(data);}pop() {return this.items.pop();}peek() {return this.items[this.items.length - 1];}size() {return this.items.length;} }

非遞歸的先序遍歷

preOrderTraversal() {console.log('先序遍歷');let root = this[ROOT];// 初始化輔助遍歷存儲的棧let stack = new Stack();let arr = []; // 用于存儲先序遍歷的順序 stack.push(root);// 如果棧不為空則一直走while (stack.size()) {let stackTop = stack.pop();// 訪問棧頂元素 arr.push(stackTop.key);stackTop.rchild && stack.push(stackTop.rchild);stackTop.lchild && stack.push(stackTop.lchild);}return arr; }

?非遞歸的中序排序

// 中序遍歷二叉樹 inorderTraversal() {// 初始化用于輔助排序的棧let stack = new Stack;let p = null; // 用于指向當前遍歷到的元素let arr = []; // 用戶記錄排序的順序p = this[ROOT];while (stack.size() || p !== null) {while (p !== null) {stack.push(p);p = p.lchild;}// 如果棧不為空出棧if (stack.size()) {p = stack.pop();arr.push(p.key);p = p.rchild;}}return arr; }

非遞歸的后序排序

?想一下，如果我們的插入順序第一個數非常大，然后后面的數字都是越來越小的會有什么問題產生呢？

下一篇文章講述這種問題的一個解決方案，平衡二叉樹。

轉載于:https://www.cnblogs.com/z937741304/p/11544054.html

總結

以上是生活随笔為你收集整理的javascript实现二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

JavaScript

上一篇：一种算法的实现，几个相同大小的div组合
下一篇：【Python】itertools之pr