BinarySearchTree

二元搜尋樹

by Chris_Walter

JavaScript

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

class BinarySearchTree{
  constructor(){
	  this.root = null;
	}
	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);
			}
		}
	}
	insert(key){
	  let newNode = new Node(key);
	  if(this.root === null){
		  this.root = newNode;
		} else{
		  this.insertNode(this.root, newNode);
		}
	}
	printNode(value){
	  console.log(value);
	}
	inOrderTraverseNode(node, callback){
	  if(node !== null){
	    this.inOrderTraverseNode(node.left, callback);
			callback(node.key);
			this.inOrderTraverseNode(node.right, callback);
		}
	}
	inOrderTraverse(callback){
	this.inOrderTraverseNode(this.root, callback);
	}
	preOrderTraverseNode(node, callback){
	  if(node !== null){
		  callback(node.key);
			this.preOrderTraverseNode(node.left, callback);
			this.preOrderTraverseNode(node.right, callback);
		}
	}
	preOrderTraverse(callback){
	  this.preOrderTraverseNode(this.root, callback);
	}
	postOrderTraverseNode(node, callback){
	  if(node !== null){
		  this.postOrderTraverseNode(node.left, callback);
			this.postOrderTraverseNode(node.right, callback);
			callback(node.key);
		}
	}
	postOrderTraverse(callback){
	  this.postOrderTraverseNode(this.root, callback);
	}
	minNode(node){
	  while(node && node.left !== null){
		  node = node.left;
		}
		return node;
	}
	min(){
	  return this.minNode(this.root);
	}
	maxNode(node){
	  while(node && node.right !== null){
		  node = node.right;
		}
		return node;
	}
	max(){
	  return this.maxNode(this.root);
	}
	searchNode(node, key){
	  if(node === null){
		  return false;
		}
		if(node.key > key){
		  return this.searchNode(node.left, key);
		} else if(node.key < key){
		  return this.searchNode(node.right,...