JavaScript數(shù)據(jù)結構與算法之二叉樹添加/刪除節(jié)點操作示例
本文實例講述了JavaScript數(shù)據(jù)結構與算法之二叉樹添加/刪除節(jié)點操作。分享給大家供大家參考,具體如下:
function Node(data,left,right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() { this.root = null; this.insert = insert; this.inOrder = inOrder; this.getMin = getMin; this.getMax = getMax; this.find = find; this.remove = remove; } function insert(data) { var n = new Node(data,null,null); if(this.root == null) { this.root = n; }else { var current = this.root; var parent; while(current) { parent = current; if(data < current.data) { current = current.left; if(current == null) { parent.left = n; break; } }else { current = current.right; if(current == null) { parent.right = n; break; } } } } } // 中序遍歷 function inOrder(node) { if(!(node == null)) { inOrder(node.left); console.log(node.show()); inOrder(node.right); } } // 先序遍歷 function preOrder(node) { if(!(node == null)) { console.log(node.show()); preOrder(node.left); preOrder(node.right); } } // 后序遍歷 function postOrder(node) { if(!(node == null)) { postOrder(node.left); postOrder(node.right); console.log("后序遍歷"+node.show()); } } // 二叉樹查找最小值 function getMin(){ var current = this.root; while(!(current.left == null)) { current = current.left; } return current.data; } // 二叉樹上查找最大值 function getMax() { var current = this.root; while(!(current.right == null)) { current = current.right; } return current.data; } // 查找給定值 function find(data) { var current = this.root; while(current != null) { if(current.data == data) { return current; }else if(data < current.data) { current = current.left; }else { current = current.right; } } return null; } function remove(data) { root = removeNode(this.root,data); } function getSmallest(node) { if (node.left == null) { return node; } else { return getSmallest(node.left); } } function removeNode(node,data) { if(node == null) { return null; } if(data == node.data) { // 沒有子節(jié)點的節(jié)點 if(node.left == null && node.right == null) { return null; } // 沒有左子節(jié)點的節(jié)點 if(node.left == null) { return node.right; } // 沒有右子節(jié)點的節(jié)點 if(node.right == null) { return node.left; } // 有2個子節(jié)點的節(jié)點 var tempNode = getSmallest(node.right); node.data = tempNode.data; node.right = removeNode(node.right,tempNode.data); return node; }else if(data < node.data) { node.left = removeNode(node.left,data); return node; }else { node.right = removeNode(node.right,data); return node; } } //代碼初始化如下: var nums = new BST(); nums.insert(23); nums.insert(45); nums.insert(16); nums.insert(37); nums.insert(3); nums.insert(99); nums.insert(22); var min = nums.getMin(); console.log(min); var max = nums.getMax(); console.log(max); var value = nums.find("45"); console.log(value); nums.remove(23);
運行結果:
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具:http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。
更多關于JavaScript相關內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)學運算用法總結》、《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript數(shù)組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調(diào)試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
相關文章
360doc網(wǎng)站不登錄就無法復制內(nèi)容的解決方法
這篇文章主要介紹了360doc網(wǎng)站不登錄就無法復制內(nèi)容的解決方法,需要的朋友可以參考下2018-01-01javascript得到XML某節(jié)點的子節(jié)點個數(shù)的腳本
得到XML某節(jié)點(pnode)的子節(jié)點個數(shù)(客戶端)2008-10-10原生JavaScript創(chuàng)建不可變對象的方法簡單示例
這篇文章主要介紹了原生JavaScript創(chuàng)建不可變對象的方法,結合簡單實例形式分析了基于原生JavaScript創(chuàng)建不可變對象的相關原理、實現(xiàn)方法與操作注意事項,需要的朋友可以參考下2020-05-05javascript的offset、client、scroll使用方法詳解
javascript的offset、client、scroll在使用過程中非常頻繁,接下來將對此進行一一介紹,需要了解的朋友可以詳細參考下2012-12-12快速獲取/設置iframe內(nèi)對象元素的幾種js實現(xiàn)方法
下面小編就為大家?guī)硪黄焖佾@取/設置iframe內(nèi)對象元素的幾種js實現(xiàn)方法。小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2016-05-05