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){
		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){
    	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){
      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;
	}    
 
    // Helper function
    // findMinNode()
    // getRootNode()
    // inorder(node)
    // preorder(node)              
    // postorder(node)
    // search(node, data)
}

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('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('preorderiterator1');
//console.log(bst.preorderiterator1(bst.root));
console.log('postorder');
console.log(bst.postorder(bst.root));
console.log('postorderiterator');
console.log(bst.postorderiterator(bst.root));
bst.remove(12);