JavaScript中的搜索二叉樹實(shí)現(xiàn)，供大家參考，具體內(nèi)容如下

二叉搜索樹（BST，Binary Search Tree），也稱二叉排序樹或二叉查找樹

二叉搜索樹是一顆二叉樹, 可以為空；如果不為空，滿足以下性質(zhì)：

非空左子樹的所有鍵值小于其根結(jié)點(diǎn)的鍵值 非空右子樹的所有鍵值大于其根結(jié)點(diǎn)的鍵值 也就是左結(jié)點(diǎn)值想<根結(jié)點(diǎn)值<右節(jié)點(diǎn)值 左、右子樹本身也都是二叉搜索樹

二叉搜索樹的操作

insert(key)：向樹中插入一個(gè)新的鍵

search(key)：在樹中查找一個(gè)鍵，如果結(jié)點(diǎn)存在，則返回true；如果不存在，則返回false

inOrderTraverse：通過中序遍歷方式遍歷所有結(jié)點(diǎn)

preOrderTraverse：通過先序遍歷方式遍歷所有結(jié)點(diǎn)

postOrderTraverse：通過后序遍歷方式遍歷所有結(jié)點(diǎn)

min：返回樹中最小的值/鍵

max：返回樹中最大的值/鍵

remove(key)：從樹中移除某個(gè)鍵

先序遍歷

①訪問根結(jié)點(diǎn) ②先序遍歷其左子樹 ③先序遍歷其右子樹

中序遍歷

①中序遍歷其左子樹②訪問根結(jié)點(diǎn)③中序遍歷其右子樹

后序遍歷

①后序遍歷其左子樹②后序遍歷其右子樹③訪問根結(jié)點(diǎn)

JavaScript 代碼實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)

// 創(chuàng)建BinarySearchTreefunction BinarySerachTree() { // 創(chuàng)建節(jié)點(diǎn)構(gòu)造函數(shù) function Node(key) { this.key = key this.left = null this.right = null } // 保存根的屬性 this.root = null // 二叉搜索樹相關(guān)的操作方法 // 向樹中插入數(shù)據(jù) BinarySerachTree.prototype.insert = function (key) { // 1.根據(jù)key創(chuàng)建對(duì)應(yīng)的node var newNode = new Node(key) // 2.判斷根節(jié)點(diǎn)是否有值 if (this.root === null) { this.root = newNode } else { this.insertNode(this.root, newNode) } } BinarySerachTree.prototype.insertNode = function (node, newNode) { if (newNode.key < node.key) { // 1.準(zhǔn)備向左子樹插入數(shù)據(jù) if (node.left === null) { // 1.1.node的左子樹上沒有內(nèi)容node.left = newNode } else { // 1.2.node的左子樹上已經(jīng)有了內(nèi)容this.insertNode(node.left, newNode) } } else { // 2.準(zhǔn)備向右子樹插入數(shù)據(jù) if (node.right === null) { // 2.1.node的右子樹上沒有內(nèi)容node.right = newNode } else { // 2.2.node的右子樹上有內(nèi)容this.insertNode(node.right, newNode) } } } // 獲取最大值和最小值 BinarySerachTree.prototype.min = function () { var node = this.root while (node.left !== null) { node = node.left } return node.key } BinarySerachTree.prototype.max = function () { var node = this.root while (node.right !== null) { node = node.right } return node.key } // 搜搜特定的值 /* BinarySerachTree.prototype.search = function (key) { return this.searchNode(this.root, key) } BinarySerachTree.prototype.searchNode = function (node, key) { // 1.如果傳入的node為null那么, 那么就退出遞歸 if (node === null) { return false } // 2.判斷node節(jié)點(diǎn)的值和傳入的key大小 if (node.key > key) { // 2.1.傳入的key較小, 向左邊繼續(xù)查找 return this.searchNode(node.left, key) } else if (node.key < key) { // 2.2.傳入的key較大, 向右邊繼續(xù)查找 return this.searchNode(node.right, key) } else { // 2.3.相同, 說明找到了key return true } } */ BinarySerachTree.prototype.search = function (key) { var node = this.root while (node !== null) { if (node.key > key) {node = node.left } else if (node.key < key) {node = node.right } else {return true } } return false } // 刪除節(jié)點(diǎn) BinarySerachTree.prototype.remove = function (key) { // 1.獲取當(dāng)前的node var node = this.root var parent = null // 2.循環(huán)遍歷node while (node) { if (node.key > key) {parent = nodenode = node.left } else if (node.key < key) {parent = nodenode = node.right } else {if (node.left == null && node.right == null) {} } } } BinarySerachTree.prototype.removeNode = function (node, key) { // 1.如果傳入的node為null, 直接退出遞歸. if (node === null) return null // 2.判斷key和對(duì)應(yīng)node.key的大小 if (node.key > key) { node.left = this.removeNode(node.left, key) } } // 刪除結(jié)點(diǎn) BinarySerachTree.prototype.remove = function (key) { // 1.定義臨時(shí)保存的變量 var current = this.root var parent = this.root var isLeftChild = true // 2.開始查找節(jié)點(diǎn) while (current.key !== key) { parent = current if (key < current.key) {isLeftChild = truecurrent = current.left } else {isLeftChild = falsecurrent = current.right } // 如果發(fā)現(xiàn)current已經(jīng)指向null, 那么說明沒有找到要?jiǎng)h除的數(shù)據(jù) if (current === null) return false } // 3.刪除的結(jié)點(diǎn)是葉結(jié)點(diǎn) if (current.left === null && current.right === null) { if (current == this.root) {this.root == null } else if (isLeftChild) {parent.left = null } else {parent.right = null } } // 4.刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) else if (current.right === null) { if (current == this.root) {this.root = current.left } else if (isLeftChild) {parent.left = current.left } else {parent.right = current.left } } else if (current.left === null) { if (current == this.root) {this.root = current.right } else if (isLeftChild) {parent.left = current.right } else {parent.right = current.right } } // 5.刪除有兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn) else { // 1.獲取后繼節(jié)點(diǎn) var successor = this.getSuccessor(current) // 2.判斷是否是根節(jié)點(diǎn) if (current == this.root) {this.root = successor } else if (isLeftChild) {parent.left = successor } else {parent.right = successor } // 3.將刪除節(jié)點(diǎn)的左子樹賦值給successor successor.left = current.left } return true } // 找后繼的方法 BinarySerachTree.prototype.getSuccessor = function (delNode) { // 1.使用變量保存臨時(shí)的節(jié)點(diǎn) var successorParent = delNode var successor = delNode var current = delNode.right // 要從右子樹開始找 // 2.尋找節(jié)點(diǎn) while (current != null) { successorParent = successor successor = current current = current.left } // 3.如果是刪除圖中15的情況, 還需要如下代碼 if (successor != delNode.right) { successorParent.left = successor.right successor.right = delNode.right } } // 遍歷方法 //handler為回調(diào)函數(shù) // 先序遍歷 BinarySerachTree.prototype.preOrderTraversal = function (handler) { this.preOrderTranversalNode(this.root, handler) } BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) { if (node !== null) { handler(node.key) this.preOrderTranversalNode(node.left, handler) this.preOrderTranversalNode(node.right, handler) } } // 中序遍歷 BinarySerachTree.prototype.inOrderTraversal = function (handler) { this.inOrderTraversalNode(this.root, handler) } BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) { if (node !== null) { this.inOrderTraversalNode(node.left, handler) handler(node.key) this.inOrderTraversalNode(node.right, handler) } } // 后續(xù)遍歷 BinarySerachTree.prototype.postOrderTraversal = function (handler) { this.postOrderTraversalNode(this.root, handler) } BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) { if (node !== null) { this.postOrderTraversalNode(node.left, handler) this.postOrderTraversalNode(node.right, handler) handler(node.key) } } /* // 測試遍歷結(jié)果(inOrderTraversal可以替換成別的遍歷方式) resultString = '' bst.inOrderTraversal(function (key) { resultString += key + ' ' }) alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 */}

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。