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``````
1. 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``````
1. 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``````
1. 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``````
1. 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``````
1. 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``````
1. 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``````
1. 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``````
1. 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``````