JavaScript implements binary search for numbers

JavaScript implements binary search for numbers

Binary search number is a kind of binary tree. Only the left child node is allowed to be smaller than the parent node, and the right child node is allowed to be larger or equal to the parent node

1. Create a Node constructor, Node, to create a new Node

function Node(val) {
	this.val = val;// The value of this object
	this.left = null;// The left child of this node
	this.right = null;// The right child of this node
}
Copy the code

2. Create a search tree constructor

function SearchTree() {
	this.root = null;/ / the root node
	this.length = 0;// The number of all nodes in the tree, including the root node
}
Copy the code

3. Add the insertTree method to the SearchTreet to insert new nodes into the tree. First, we need to judge whether the root node is empty, and then iterate from the root node. If the value of the node to be inserted is smaller than that of the parent node, it will be the left child node of the parent node, and vice versa. Return the object after the final insertion and increment length by one

SearchTree.prototype.insertTree = function(val) {
		// Create a node
		let node = new Node(val);
		if (this.root === null) {
		// If our root node is null, an initial search tree is required
			this.root = node;
			this.length++;
			return this.root;
		} else {
			let curr = this.root;
			while (true) {
				// Iterate over the binary tree, placing the one smaller than the root node to the left and vice versa
				if (val < curr.val) {
					if(curr.left ! = =null) {
					// Continue iterating if left is not empty
						curr = curr.left;
					} else {
						curr.left = node;
						// Exit the while loop
						break; }}else {
					if(curr.right ! = =null) {
						curr = curr.right;
					} else {
						curr.right = node;
						break; }}}}this.length++;
		return node;
	},
Copy the code

4. The former sequence traversal

SearchTree.prototype.prevErgodic  = function(node, arr = []) {
		if(node ! = =null) {
			arr.push(node.val)
			this.prevErgodic  (node.left, arr);
			this.prevErgodic  (node.right, arr)
		}
		return arr
	}
Copy the code

5. In the sequence traversal

SearchTree.prototype.centerErgodic = function(node, arr = []) { 
		if(node ! = =null) {
			// Ascending sort
			this.centerErgodic (node.left, arr);
			arr.push(node.val);
			this.centerErgodic (node.right, arr);
			// Sort in descending order
			//this.centerErgodic (node.right, arr);
			//arr.push(node.val);
			//this.centerErgodic (node.left, arr);
		}
		return arr;
	}
Copy the code

6. After the sequence traversal

SearchTree.prototype.nextErgodic.function(node, arr = []) { 
		if(node ! = =null) {
			this.nextErgodic(node.left, arr);
			this.nextErgodic(node.right, arr);
			arr.push(node.val);
		}
		return arr;
	}
Copy the code

7. Obtain the minimum value, traversing from the root node to the left node to the leaf node, the leaf node is the minimum value

SearchTree.prototype.getMin = function(node) {
		let curr = node || this.root;
		if (curr === null) {
			return false;
		} else {
			while(curr.left ! = =null) {
				curr = curr.left
			}
			return curr.val
		}
	}
Copy the code

8. The maximum value is obtained by traversing the right node from the root node to the leaf node, which is the maximum value

SearchTree.prototype.getMax = function(node) {
		let curr = node || this.root;
		if (curr === null) {
			return false;
		} else {
			while(curr.right! = =null) {
				curr = curr.right
			}
			return curr.val
		}
	}
Copy the code

9. Checks if the value exists, returns this object if it does, false otherwise

SearchTree.prototype.getItem = function(node, item) {
		if (this.root === null) {
			return false
		} else {
			let curr = node;
			if (curr === null) {
				return false;
			} else {
				if (item < curr.val) {
					return this.getItem(curr.left, item);
				} else if (item === curr.val) {
					return curr;
				} else if (item > curr.val) {
					return this.getItem(curr.right, item); }}}}Copy the code

The test code

// Create an instance
const searchTree = new SearchTree();
// Create an array and loop in nodes to the searchTree
let max = 100;
let arr = [];
for (let index = 0; index < max; index++) {
	let item = Math.floor(Math.random() * max);
	arr.push(item);
	searchTree.insertTree(item)
}
console.log(searchTree)
// Prints the original array
console.log(arr)
// Prints the array traversed before
console.log(searchTree.prevErgodic(searchTree.root))
// Prints an array of sequential traversal
console.log(searchTree.centerErgodic(searchTree.root))
// Prints the ascending array, compared with the middle-traversal array
console.log(arr.sort((a,b) = >a - b))
// Print the sequential traversal array
console.log(searchTree.nextErgodic(searchTree.root))
// Get the minimum value
console.log(searchTree.getMin())
// Get the maximum value
console.log(searchTree.getMax())
// Get the specified value node
console.log(searchTree.getItem(searchTree.root, searchTree.getMax()))
Copy the code