javascript數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹實(shí)現(xiàn)方法
本文實(shí)例講述了javascript二叉搜索樹實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:
二叉搜索樹:顧名思義,樹上每個(gè)節(jié)點(diǎn)最多只有二根分叉;而且左分叉節(jié)點(diǎn)的值 < 右分叉節(jié)點(diǎn)的值 。
特點(diǎn):插入節(jié)點(diǎn)、找最大/最小節(jié)點(diǎn)、節(jié)點(diǎn)值排序 非常方便
二叉搜索樹-javascript實(shí)現(xiàn)
<script type="text/javascript"> // <![CDATA[ //打印輸出 function println(msg) { document.write(msg + " "); } //節(jié)點(diǎn)類 var Node = function (v) { this.data = v; //節(jié)點(diǎn)值 this.left = null; //左節(jié)點(diǎn) this.right = null; //右節(jié)點(diǎn) } //二叉搜索樹類 var BinarySearchTree = function () { this.root = null; //初始化時(shí),根節(jié)點(diǎn)為空 //插入節(jié)點(diǎn) //參數(shù):v 為節(jié)點(diǎn)的值 this.insert = function (v) { var newNode = new Node(v); if (this.root == null) { //樹為空時(shí),新節(jié)點(diǎn),直接成為根節(jié)點(diǎn) this.root = newNode; return; } var currentNode = this.root; //工作“指針”節(jié)點(diǎn)(從根開始向下找) var parentNode = null; while (true) { parentNode = currentNode; if (v < currentNode.data) { //當(dāng)前節(jié)點(diǎn)的值 > 目標(biāo)節(jié)點(diǎn)的值 //應(yīng)該向左插,工作節(jié)點(diǎn)移到左節(jié)點(diǎn) currentNode = currentNode.left; if (currentNode == null) { //沒有左節(jié)點(diǎn),則新節(jié)點(diǎn),直接成為左節(jié)點(diǎn) parentNode.left = newNode; return; //退出循環(huán) } } else { //否則向右插,工作節(jié)點(diǎn)移到右節(jié)點(diǎn) currentNode = currentNode.right; if (currentNode == null) { parentNode.right = newNode; return; } } } } //查找最小節(jié)點(diǎn) this.min = function () { var p = this.root; //工作節(jié)點(diǎn) while (p != null && p.left != null) { p = p.left; } return p; } //查找最大節(jié)點(diǎn) this.max = function () { var p = this.root; //工作節(jié)點(diǎn) while (p != null && p.right != null) { p = p.right; } return p; } //中序遍歷 this.inOrder = function (rootNode) { if (rootNode != null) { this.inOrder(rootNode.left); //先左節(jié)點(diǎn) println(rootNode.data); //再根節(jié)點(diǎn) this.inOrder(rootNode.right); //再右節(jié)點(diǎn) } } //先序遍歷 this.preOrder = function (rootNode) { if (rootNode != null) { println(rootNode.data); //先根 this.preOrder(rootNode.left); //再左節(jié)點(diǎn) this.preOrder(rootNode.right); //再右節(jié)點(diǎn) } } //后序遍歷 this.postOrder = function (rootNode) { if (rootNode != null) { this.postOrder(rootNode.left); //先左節(jié)點(diǎn) this.postOrder(rootNode.right); //再右節(jié)點(diǎn) println(rootNode.data); //再根節(jié)點(diǎn) } } } //以下是測試 var bTree = new BinarySearchTree(); //《沙特.算法設(shè)計(jì)技巧與分析》書上圖3.9 左側(cè)的樹 bTree.insert(6); bTree.insert(3); bTree.insert(8); bTree.insert(1); bTree.insert(4); bTree.insert(9); println('中序遍歷:') bTree.inOrder(bTree.root); println("<br/>"); println("先序遍歷:"); bTree.preOrder(bTree.root); println("<br/>"); println("后序遍歷:"); bTree.postOrder(bTree.root); println("<br/>"); var minNode = bTree.min(); println("最小節(jié)點(diǎn):" + (minNode == null ? "不存在" : minNode.data)); println("<br/>"); var maxNode = bTree.max(); println("最大節(jié)點(diǎn):" + (maxNode == null ? "不存在" : maxNode.data)); // ]]> </script> <!--中序遍歷: 1 3 4 6 8 9 <br> 先序遍歷: 6 3 1 4 8 9 <br> 后序遍歷: 1 4 3 9 8 6 <br> 最小節(jié)點(diǎn):1 <br> 最大節(jié)點(diǎn):9-->
輸出結(jié)果:
中序遍歷: 1 3 4 6 8 9 先序遍歷: 6 3 1 4 8 9 后序遍歷: 1 4 3 9 8 6 最小節(jié)點(diǎn):1 最大節(jié)點(diǎn):9
希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
JavaScript單例模式實(shí)現(xiàn)自定義彈框
這篇文章主要為大家詳細(xì)介紹了JavaScript單例模式實(shí)現(xiàn)自定義彈框,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-10-10轉(zhuǎn)換layUI的數(shù)據(jù)表格中的日期格式方法
今天小編就為大家分享一篇轉(zhuǎn)換layUI的數(shù)據(jù)表格中的日期格式方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09網(wǎng)易JS面試題與Javascript詞法作用域說明
Javascript函數(shù)在定義它們的作用域里運(yùn)行,而不是在執(zhí)行它們的作用域里運(yùn)行。2010-11-11刷新頁面實(shí)現(xiàn)方式總結(jié)(HTML,ASP,JS)
多種方法實(shí)現(xiàn)頁面的刷新代碼2008-11-11webpack+vue-cil中proxyTable處理跨域的方法
這篇文章主要介紹了webpack+vue-cil中proxyTable處理跨域的方法,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-07-07使用 JavaScript 進(jìn)行函數(shù)式編程 (一) 翻譯
本文是函數(shù)式編程系列的第一篇文章。這里我會(huì)簡要介紹一下編程范式,然后會(huì)直接介紹使用 Javascript 進(jìn)行函數(shù)式編程的概念,因?yàn)?JavsScript 是最被認(rèn)可的函數(shù)式程序語言之一。我們鼓勵(lì)讀者通過參考資料部分進(jìn)一步了解這一迷人的概念2015-10-10JavaScript幾種形式的樹結(jié)構(gòu)菜單
今天我主要講3種不同展示的JavaScript樹結(jié)構(gòu)菜單,分別是懸浮層樹(Tree)、右鍵菜單樹(ContextMenu)和節(jié)點(diǎn)樹(TreeMenu),目前都支持無限級(jí)層次。2010-05-05