BST的简单实现

最基础的数据结构往往会有最关键的作用，理解这些基础的数据结构能做什么，以及它们不能做什么对于我们理解数据结构的本质有关键的作用。

const Random = require("random-js").Random;
const MersenneTwister19937 = require("random-js").MersenneTwister19937;
const random = new Random(MersenneTwister19937.autoSeed());
class Node {
    constructor(data){
		this.data = data;
 		this.left = null;
		this.right = null;
	}
}

class BinarySearchTree {
	constructor(){
		this.root = null;
	}
	// function to be implemented
    // insert(data)
	insert(data) {
		let newNode = new Node(data);
		if (this.root === null) {
			this.root = newNode;
 		} else {
 			this.insertNode(this.root,newNode);
 		}
	}
	insertNode(node, newNode) {
		if (newNode.data < node.data) {//insert left tree
			if (node.left === null){
				node.left = newNode;
 			} else {
 				this.insertNode(node.left, newNode);
 			}
 		} else {//greater than value, insert right tree
 			if (node.right === null) {
				node.right = newNode;
 			} else {
 				this.insertNode(node.right, newNode);
 			}
 		}
	}
    // remove(data)
    remove(data){
		this.root = this.removeNode(this.root,data);
	}   
	removeNode(node,data){
		if (node === null){
			return null;
 		}else if (data < node.data) {
			node.left = this.removeNode(node.left, data);
			return node;
 		}else if (data > node.data){
			node.right = this.removeNode(node.right, data);
			return node;
 		} else {
 			//没有左右节点
			if (node.left === null && node.right === null){
				node = null;
				return null;
 			}
			//has right no left
			if (node.left === null){
				node = node.right;
				return node;
 			}
 			// has left no right
 			if (node.right === null){
				node = node.left;
				return node;
 			}
 			// both left and right
 			let aux = findMinNode(node.right);
			node.data = aux.data;
			node.right = this.removeNode(node.right,aux.data);
			return node;
 		}
	}
 	//recursive to find minimum node
    findMinNode(node){
        // if left of a node is null
        // then it must be minimum node
        if(node.left === null) {
            return node;
        } else {
            return this.findMinNode(node.left);
	    }  
	}  

    inOrder(node) {
      const res = []
      if (node === null) {
        return res;
      }
      const leftRes = this.inOrder(node.left);
      for (let i = 0 ; i< leftRes.length; i++) {
        res.push(leftRes[i]);
      }
      res.push(node.data);
      const rightRes = this.inOrder(node.right);
      for (let i = 0 ; i< rightRes.length; i++) {
        res.push(rightRes[i]);
      }
      return res;
    }

	inorder(node){
		if (node!== null){
			this.inorder(node.left);
			console.log(node.data);
			this.inorder(node.right);
 		}
	}
    inorderiterator(node) {
      const stack = [];
      const reversed = [];
      let curr = node;
      while(stack.length || curr) {
        while(curr) {
          stack.push(curr);
          curr = curr.left;
        }
        curr = stack.pop();
        reversed.push(curr.data);
        curr = curr.right;
      }
      return reversed;
    }

    preOrder(node) {
      const res = [];
      if (node === null) {
        return res;
      }
      res.push(node.data);
      const leftRes = this.preOrder(node.left);
      for (let i = 0 ; i< leftRes.length; i++) {
        res.push(leftRes[i]);
      }
      const rightRes = this.preOrder(node.right);
      for (let i = 0 ; i< rightRes.length; i++) {
        res.push(rightRes[i]);
      }
      return res;
    }

	preorder(node){
    	if(node !== null){
        	console.log(node.data);
        	this.preorder(node.left);
        	this.preorder(node.right);
    	}
	}
    preorderiterator(node) {
      const stack = [node];
      const traversed = [];
      let curr;
      while(stack.length) {
        curr = stack.pop();
        traversed.push(curr.data);
        if (curr.right) {
          stack.push(curr.right);
        }
        if (curr.left) {
          stack.push(curr.left);
        }
      }
      return traversed;
    }

    preorderiterator1(node) {
      const stack = [];
      const traversed = [];
      let curr = node;
      while(stack.length || curr) {
        while(curr){
          traversed.push(curr.data);
          stack.push(curr);
          curr = curr.left;
        }
        curr = stack.pop();
        curr = curr.right;
      }
      return traversed;
    }

    postOrder(node) {
      const res = [];
      if (node === null) {
        return res;
      }
      const leftRes = this.postOrder(node.left);
      for (let i = 0 ; i < leftRes.length; i++ ) {
        res.push(leftRes[i]);
      }
      const rightRes = this.postOrder(node.right);
      for (let i = 0 ; i < rightRes.length; i++ ) {
        res.push(rightRes[i]);
      }
      res.push(node.data);
      return res;
    }
  
	postorder(node){
      if(node !== null){
        this.postorder(node.left);
        this.postorder(node.right);
        console.log(node.data);
      }
	}

    postorderiterator(node) {
      const s1 = [node];
      const s2 = [];
      const reversed = [];
      let curr;
      while(s1.length) {
        curr = s1.pop();
        if (curr.left) {
          s1.push(curr.left);
        }
        if (curr.right) {
          s1.push(curr.right);
        }
        s2.push(curr);
      }
      while(s2.length) {
        curr = s2.pop();
        reversed.push(curr.data);
      }
      return reversed;
    }
  
	getRootNode(){
    	return this.root;
	} 
	search(node, data){
   		// if trees is empty return null
    	if(node === null)
        	return null;
 
    	// if data is less than node's data
    	// move left
    	else if(data < node.data)
        	return this.search(node.left, data);
 
    	// if data is more than node's data
    	// move right
    	else if(data > node.data)
        	return this.search(node.right, data);
 
    	// if data is equal to the node data
    	// return node
    	else
        	return node;
	}

    /**
     * 这个方法采用的是遍历
     */
    maxDepth(root) {
      this.res = 0;
      this.depth = 0;
      this.leaves = 0;
      this.travel(root);
      return this.res;
    }

    /**
     * 这个方法采用的是分治
     */
    maxDepthRecursive(root) {
      if (root===null) {
        return 0;
      }
      const leftDepth = this.maxDepthRecursive(root.left);
      const rightDepth = this.maxDepthRecursive(root.right);
      //由子树的深度推测出当前树的深度
      return Math.max(leftDepth,rightDepth) + 1;
    }

    travel(root) {
      if (root === null) {
        return;
      }
      this.depth++;
      if (root.left === null && root.right === null) {
        this.leaves++;
        this.res = Math.max(this.depth, this.res);
      }
      this.travel(root.left);
      this.travel(root.right);
      this.depth--;
    }

    printLevel(root, level) {
      if (root === null) {
        return;
      }
      console.log('current data:'+ root.data + ', it\'s level is:'+level);
      this.printLevel(root.left, level+1);
      this.printLevel(root.right, level+1);
    }

    calculateNodeCount(root) {
      if (root === null) {
        return 0;
      }
      const ltCount = this.calculateNodeCount(root.left);
      const rtCount = this.calculateNodeCount(root.right);
      //这部分计算需要知道左右子节点的信息后才能计算，因此放在最后
      return ltCount+rtCount+1;
    }

    /**
     * 反转左右子树节点 遍历递归思维
     */
    reverseLR(root) {
      if (root === null) {
        return;
      }
      const temp = root.left;
      root.left = root.right;
      root.right = temp;
      //注意，以上三行代码放在当前节点的前序位置，也可以放在后序位置
      //如果放在中序位置会怎么样呢？
      this.reverseLR(root.left);
      this.reverseLR(root.right);
    }

    /**
     * 反转左右子树节点 分治递归思维
     */
    invertTree(root) {
      if (root === null) {
        return null;
      }
      const left = this.invertTree(root.left);
      const right = this.invertTree(root.right);
      root.left = right;
      root.right = left;
      return root;
    }

    connect(root) {
      //这个算法需要完全二叉树
      if (root === null) {
        return null;
      }
      this.connectTravel(root.left, root.right);
    }

    connectTravel(node1, node2) {
      //这里需要把node1和node2，抽象看做一个整体
      if (node1 === null || node2 === null) {
        return;
      }
      node1.next = node2;
      this.connectTravel(node1.left, node1.right);
      this.connectTravel(node1.right, node1.right);
      this.connectTravel(node1.right, node2.left);
    }

    flatten(root) {
      if (root === null) {
        return;
      }
      this.flatten(root.left);
      this.flatten(root.right);
      //注意，后序中有三步操作
      //左右子树已经展平
      const left = root.left;
      const right = root.right;
      //左子树接上当前节点的右节点
      root.left = null;
      root.right = left;
      //找到当前节点的有段
      const p = root;
      while(p.right !==null) {
        p = p.right;
      }
      p.next = right;
    }

    isValidBst(root) {
      return this.isValidBstHelper(root, null,null);
    }

    isValidBstHelper(root, min, max) {
      if (root === null) {
        return true;
      }
      //判断左子树
      if (min!==null && min.data >= root.data) {
        return false;
      }
      //判断左子树
      if (max!==null && max.data <= root.data) {
        return false;
      }
      return this.isValidBstHelper(root.left,min,root) &&
        this.isValidBstHelper(root.right,root,max);
    }

    isValidBst1(root) {
      if (root === null) {
        return true;
      }
      const leftValid = this.isValidBst1(root.left);
      const rightValid = this.isValidBst1(root.right);
      //判断当前节点是否合法
      if (root.left!== null && root.data<= root.left.data) {
        return false;
      }
      if (root.right!== null && root.data>= root.right.data) {
        return false;
      }
      return leftValid && rightValid;
    }

    static buildTree(arrays) {
      return BinarySearchTree.build(arrays,0, arrays.length-1);
    }

    static build(arrays,start, end) {
      //如果只有一个节点即start===end，那么需要继续递归，
      //因此base case is below
      if (start > end) {
        return null;
      }
      //获取当前迭代的根节点值和索引，分成两半分别迭代，返回值是当前的根节点
      let index = -1,maxVal = Number.MIN_VALUE;
      for (let i = start; i <= end; i++) {
        if (arrays[i] > maxVal ) {
          maxVal = arrays[i];
          index = i;
        }
      }
      const root = new Node(maxVal);
      const left = BinarySearchTree.build(arrays, start, index-1);
      const right = BinarySearchTree.build(arrays, index+1, end);
      root.left = left;
      root.right = right;
      return root;
    }

    static buildTree1(preOrders, inOrders){
      return BinarySearchTree.build1(preOrders,0, preOrders.length-1,
                                   inOrders,0,inOrders.length-1);
    }

    static build1(preOrders, preStart,preEnd,inOrders, inStart,inEnd){
      if (preStart>preEnd) {
        return null;
      }
      const rootVal = preOrders[preStart];
      let rootIndex = -1;
      for (let i = inStart ;i <= inEnd; i++) {
        if (rootVal === inOrders[i]) {
          rootIndex = i;
          break;
        }
      }
      // 通过中序计算左边子树的个数
      const leftSize = rootIndex-inStart;
      const rootNode = new Node(rootVal);
      const left = BinarySearchTree.build1(preOrders,preStart+1,preStart+leftSize,
                                         inOrders,inStart, rootIndex-1);
      const right = BinarySearchTree.build1(preOrders,preStart+leftSize+1,preEnd,
                                         inOrders,rootIndex+1, inEnd);
      rootNode.left = left;
      rootNode.right = right;
      return rootNode;
    }

    static buildTree2(inOrders,postOrders) {
      return BinarySearchTree.build2(inOrders,0, inOrders.length-1,
                                   postOrders,0,postOrders.length-1);
    }

    static build2(inOrders, inStart,inEnd ,
                     postOrders, postStart,postEnd) {
      if (postStart > postEnd) {
        return null;
      }
      const rootVal = postOrders[postEnd];
      let rootIndex = -1;
      for (let i = inStart ;i <= inEnd; i++) {
        if (rootVal === inOrders[i]) {
          rootIndex = i;
          break;
        }
      }
      // 通过中序计算左边子树的个数
      const leftSize = rootIndex-inStart;
      const rootNode = new Node(rootVal);
      const left = BinarySearchTree.build2(inOrders,inStart,rootIndex-1,
                                         postOrders,postStart, postStart+ leftSize-1);
      const right = BinarySearchTree.build2(inOrders,rootIndex+1,inEnd,
                                         postOrders,postStart+ leftSize, postEnd-1);
      rootNode.left = left;
      rootNode.right = right;
      return rootNode;
    }
    // Helper function
    // findMinNode()
    // getRootNode()
    // inorder(node)
    // preorder(node)              
    // postorder(node)
    // search(node, data)
}
const buildedBst = new BinarySearchTree();
const root = BinarySearchTree.buildTree([4,9,15,8,6,2]);
buildedBst.root = root;
console.log(buildedBst.preorder(buildedBst.root));

const newBst = new BinarySearchTree();
const rootNew = BinarySearchTree.buildTree1([3,9,20,15,7],[9,3,15,20,7]);
newBst.root = rootNew;
console.log(newBst.preorder(newBst.root));

const newBst1 = new BinarySearchTree();
const rootNew1 = BinarySearchTree.buildTree2([5,2,6,4,7,1,8,3,9],[5,6,7,4,2,8,9,3,1]);
newBst1.root = rootNew1;
console.log(newBst1.inorder(newBst1.root));

const bst = new BinarySearchTree();
const newBet = new BinarySearchTree();
for (let i = 0 ; i< 20; i++){
	const value = random.integer(1, 100);
	newBet.insert(value);
}
console.log('inorder newBet');
//console.log(newBet.inorder(newBet.root));
bst.insert(10);
bst.insert(12);
bst.insert(8);
bst.insert(15);
bst.insert(9);
bst.insert(14);
// console.log('reverse left and right');
// bst.reverseLR(bst.root);

console.log('bst is valid or not:' + bst.isValidBst1(bst.root));

console.log('print level is:');
bst.printLevel(bst.root,1);
const bstCount = bst.calculateNodeCount(bst.root);
console.log('bst calculate count is:'+bstCount);
console.log('maxDepth:'+bst.maxDepth(bst.root));
console.log('leaves count:'+bst.leaves);
console.log('maxDepth1:'+bst.maxDepthRecursive(bst.root));
console.log('inorder');
console.log(bst.inorder(bst.root));
console.log('inOrder');
console.log(bst.inOrder(bst.root));
//console.log('inorderiterator');
//console.log(bst.inorderiterator(bst.root));
console.log('preorder');
console.log(bst.preorder(bst.root));
console.log('preOrder');
console.log(bst.preOrder(bst.root));
//console.log('preorderiterator1');
//console.log(bst.preorderiterator1(bst.root));
console.log('postorder');
console.log(bst.postorder(bst.root));
console.log('postOrder');
console.log(bst.postOrder(bst.root));
console.log('postorderiterator');
console.log(bst.postorderiterator(bst.root));


bst.remove(12);