小编给大家分享一下JavaScript中二叉树如何实现查找最小值、最大值、给定值算法,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
具体如下:
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.preOrder = preOrder; this.inOrder = inOrder; this.postOrder = postOrder; this.getMin = getMin;//查找最小值 this.getMax = getMax;//查找最大值 this.find = find;//查找给定值 } 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()); } } /* *查找BST上的最小值 *因为较小的值总是在左子节点上,在BST上查找最小值,只需要遍历左子树,直到找到最后一个节点。*/ function getMin(){ var current = this.root; while(!(current.left == null)) { current = current.left; } // return current;//返回最小值所在的节点 return current.data;//返回最小值 } /* *查找BST上的最大值 *因为较大的值总是在右子节点上,在BST上查找最大值,只需要遍历右子树,直到找到最后一个节点。*/ function getMax() { var current = this.root; while(!(current.right == null)) { current = current.right; } // return current;//返回最大值所在的节点 return current.data;//返回最大值 } /* *查找给定值 *在BST上查找给定值,需要比较该值和当前节点上的值的大小。 *通过比较,就能确定如果给定值不在当前节点时,该向左遍历还是向右遍历。*/ 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; } 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 find = nums.find("88"); console.log( find); if(find != null){ console.log("给定值为: " + find.data); console.log("给定值为: " + find.show()); } var find = nums.find("37"); console.log( find); if(find != null){ console.log("给定值为: " + find.data); console.log("给定值为: " + find.show()); }
运行结果:
看完了这篇文章,相信你对“JavaScript中二叉树如何实现查找最小值、最大值、给定值算法”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。