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());}