Remember at the beginning of the study of data structure with C language to achieve, learn so long front-end want to use JavaScript to achieve, incidentally review the data structure.

So what is a sorted binary tree, a sorted binary tree is a binary tree that has the following characteristics, right

  1. If the left subtree is not empty, then the values of all nodes in the left subtree are less than or equal to itsRoot knotThe value of the point

  2. If the right subtree is not empty, then the value of all nodes in the right subtree is greater than or equal to the value of its root node,

  3. The left and right subtrees are also binary sort trees respectively

In this graph, for example, the value on the left is always less than the value on the right




Let’s implement a wave in code

The first is the structure of the tree and the root node

var Node = functionLeft = null this.right = null this.key = key} var root = null // root nodeCopy the code


The basic process of binary tree insertion is to compare the number to be inserted with the value of the current node. According to the characteristics of sorting binary tree, the value on the left is always smaller than the value on the right

var insertNode = function(node,newNode){        if(node.key > newNode.key){// The value to be inserted is less than the current node, the left subtree traversesif(node.left === null){                node.left = newNode                return             }else{                insertNode(node.left,newNode)            }        }else if(node.key <= newNode.key){// The value to be inserted is less than the current node, right subtree traversalif(node.right === null){                node.right = newNode            }else{                insertNode(node.right,newNode)            }        }    }
Copy the code


After the insertion is successful, we respectively realize the pre-order, middle-order and post-order traversal of the sorted binary tree

A front-order traversal visits the root node first, followed by the left and right nodes

A middle-order traversal visits the left node first, followed by the root and right nodes

A back-order traversal visits the left and right nodes first and the root node last

The following code

 var inOrderTraverseNode = function(node,callback){// order traversalif(node ! == null){inOrderTraverseNode(node.left)            console.log(node.key)            inOrderTraverseNode(node.right)        }    }
   
    var preOrderTraverseNode = function(node,callback){// go throughif(node ! == null){ console.log(node.key) preOrderTraverseNode(node.left) preOrderTraverseNode(node.right) } } var afterOrderTraversNode =function(node,callback){// Backorder traversalif(node ! == null){ afterOrderTraversNode(node.left) afterOrderTraversNode(node.right) console.log(node.key) } }Copy the code


Find the maximum and minimum value of the binary tree. According to the characteristics of sorting the binary tree, we can quickly know that the maximum value is in the rightmost leaf node and the minimum value is in the leftmost leaf node

var Max = function(node) {/ / Maxif(node.right ! == null){ maxNum = Max(node.right) }else{            return node.key        }        return maxNum    }
    var Min = function(node) {/ / minimum valueif(node.left ! == null){ minNum = Min(node.left)        }else{            return node.key        }        return minNum    }Copy the code

Finding a specified value in a sorted binary tree is also easy, bound by the root node, smaller than the left to the left, smaller than the right to the right

var Search = function(node,key){// Find the specified valueif(node.key === key){                return true            }else{                if(key < node.key && node.left ! =null){return Search(node.left,key)                }else if(key > node.key && node.left ! =null){return Search(node.right,key)                }else{                    return false}}}Copy the code

The most troublesome operation is the operation of deleting nodes, which needs to be divided into three situations: deleting nodes without subtrees, deleting nodes as monadic trees, deleting nodes with two subtrees,

No subtree is the easiest, just delete it

 if(node.left === null && node.right === null){                node = null                return node            }Copy the code

With monad trees: like the picture below. Now I’m going to delete the 3,




It will become a



The code implementation is as follows

else if(node.left ! == null && node.right === null){ node = node.leftreturn node            }else if(node.left === null && node.right ! == null){ node = node.rightreturn node            }Copy the code

Finally have two subtrees node is deleted, in order to maintain our sorting the nature of the binary tree, first of all, we find you want to delete the node tree, the smallest value of the right word according to the characteristics of the ordered binary tree, find the minimum value must be greater than all the values you want to delete the node left subtree, because to find the value of the node of the minimum for right, so less than you want to delete the node right subtree of all values, We replace the value to be deleted with the minimum value found, and finally delete the node with the minimum value found in the first place. The basic process is equivalent to replacing the value of the node to be deleted.

In the picture below, I’m going to delete the 3



Follow the idea above, find the 4 instead of the 3, and then delete the node where the 4 was originally found



It still satisfies the characteristics of sorted binary trees

else if(node.left ! == null && node.right ! == null){ var minNode = finMinNode(node.right)                node.key = minNode.key                node.right = Remove(node.right,minNode.key)                return node            }Copy the code

I’ve done all the basic things to sort binary trees here

Complete code in GitHub (GitHub small stars), I put the bidirectional list also use JavaScript to achieve the next, you can also look at the need