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.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) {    // 没有子节点的节点    if(node.left == null && node.right == null) {      return null;    }     // 没有左子节点的节点    if(node.left == null) {      return node.right;    }    // 没有右子节点的节点    if(node.right == null) {      return node.left;    }    // 有2个子节点的节点    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);