数据结构-javascript实现【二叉树】

二叉树中的节点最多只能有两个节点：一个是左侧子节点，另一个是右侧子节点。

二叉搜索树是二叉树的一种，但是它只允许你在左侧节点存储比父节点小的值，在右侧节点存储比父节点大或者等于的值。

1. 二叉搜索树的方法

insert(key): 向树中插入一个新的键

search(key): 在书中查找一个键是否存在

inOrderTraverse(): 通过中序遍历方式遍历所有节点, 以从最小到最大的顺序访问节点。

preOrderTraverse(): 通过先序遍历方式遍历所有节点，以优先于后代节点的顺序访问每个节点。

postOrderTraverse(): 通过后序遍历方式遍历所有节点，先访问节点的后代节点，再访问节点本身。

min(): 返回树中的最小值

max(): 返回树中的最大值

remove(key): 从树中移除某个值

2. 二叉搜索树的实现

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  insert(key) {
    const newNode = new Node(key);
    if( this.root === null){
      this.root = newNode;
    }
    else {
      this._insertNode(this.root, newNode);
    }
  }

  _insertNode(node, newNode) {
    if(newNode.key < node.key){
      if(node.left === null){
        node.left = newNode;
      }
      else{
        this._insertNode(node.left, newNode);
      }
    }
    else{
      if(node.right === null){
        node.right = newNode;
      }
      else {
        this._insertNode(node.right, newNode);
      }
    }
  }

  inOrderTraverse(callback) {
    this._inOrderTraverseNode(this.root, callback);
  }

  _inOrderTraverseNode(node, callback) {
    if(node !== null){
      this._inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this._inOrderTraverseNode(node.right, callback);
    }
  }

  preOrderTraverse(callback){
    this._preOrderTraverseNode(this.root, callback);
  }

  _preOrderTraverseNode(node, callback){
    if(node !== null){
      callback(node.key);
      this._preOrderTraverseNode(node.left, callback);
      this._preOrderTraverseNode(node.right, callback);
    }
  }

  postOrderTraverse(callback) {
    this._postOrderTraverseNode(this.root, callback);
  }

  _postOrderTraverseNode(node, callback) {
    if(node !== null){
      this._postOrderTraverseNode(node.left, callback);
      this._postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
  
  min(){
    return this._minNode(this.root);
  }

  _minNode(node){
    if(node){
      while(node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  }

  max() {
    return this._maxNode(this.root);
  }

  _maxNode(node) {
    if(node) {
      while(node && node.right !== null){
        node = node.right;
      }
      return node.key;
    }
    return null;
  }

  search(key) {
    return this._searchNode(this.root, key);
  }

  _searchNode(node, key){
    if(node === null) return false;
    if( key < node.key){
      return this._searchNode(node.left, key);
    } else if( key > node.key) {
      return this._searchNode(node.right, key);
    } else {
      return true; 
    }
  }

  remove(key) {
    this.root = this._removeNode(this.root, key);
  }

  _removeNode(node, key) {
    if( node === null) return null;
    if( key < node.key){
      node.left = this._removeNode(node.left, key);
      return node;
    }
    else if( key > node.key) {
      node.right = this._removeNode(node.right, key);
      return node;
    }
    else {
      if(node.left === null && node.right === null){
        node = null;
        return node;
      }

      if(node.left === null) {
        node = node.right;
        return node;
      }
      else if (node.right === null){
        node = node.left;
        return node;
      }

      const aux = this.min(node.right);
      node.key = aux.key;
      node.right = this._removeNode(node.right, aux.key);
      return node;
    }

  }

}

function Node(key){
  this.key = key;
  this.left = null;
  this.right = null;
}

const tree = new BinarySearchTree();
console.log('向二叉树中增加值 11，7，15，5，3');
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
console.log('========== 中序遍历==========');
tree.inOrderTraverse((value) => {
  console.log(value);
});

console.log('========== 先序遍历==========');
tree.preOrderTraverse((value) => {
  console.log(value);
});

console.log('========== 后序遍历==========');
tree.postOrderTraverse((value) => {
  console.log(value);
});

const min = tree.min();
console.log('树中的最小值是: ', min);
const max = tree.max();
console.log('树中的最大值是: ', max);
console.log('在树中搜索5: ', tree.search(5));

tree.remove(5);
const treeArray = [];
tree.inOrderTraverse((value) => {
  treeArray.push(value);
});
console.log('移除树中的节点5: ', treeArray.join(','));