JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例
需积分: 3 64 浏览量
2020-12-09
03:49:45
上传
评论
收藏 48KB PDF 举报
JavaScript数据结构与算法之二叉树实现查找最小值、最大数据结构与算法之二叉树实现查找最小值、最大
值、给定值算法示例值、给定值算法示例
本文实例讲述了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上查找最小值，只需要遍历左子树，直到找到最后一个节点。*/
资源评论
