preface

I’ve been studying binary trees, duplicating and summarizing this stuff. It’s a good idea to learn data structures in school

The body of the

Binary Search tree BST Binary Search tree BST Binary Search tree BST Binary Search tree BST Binary Search tree BST Binary Search tree

Binary search tree

What is a binary search tree, perhaps in conjunction with its properties

Binary search tree is a binary tree that can be null. 2. If it is not null, the following properties must be met: 1. All keys of the non-empty left subtree are less than those of the root node. 2. All keys of the non-empty right subtree are greater than those of the root node. Left and right subtrees are binary search trees themselves. The summary is that, for each node, the left with the lower key value is on the left, and the right with the higher key value is on the right (small left and large right). Let's look at a picture to get a better ideaCopy the code

If you take root 5, everything smaller than it is in the left subtree, everything larger than it is in the right subtree and everything else is in the right subtree, that's a binary search treeCopy the code

Code implementation

As we can see from the above figure, the binary tree is actually composed of nodes, which have key values and two arrows pointing to the left and right. Therefore, it can be regarded as a node with three attributes. We first create a BinarySearchTree class

BinarySearchTree class

Function BinarySearchTree() {// Create a Node class function Node(key) {// This. key = key this.left = null this.right = null} // root this.root = null}Copy the code

methods

Then there are the methods, which use the recursive idea, the first one is the method of inserting nodes

Insert (key): Inserts a new key into the tree
Principle: By recursive method, the new Node is compared with the root Node and other nodes. The new Node is placed on the right side if it is larger than the root Node, and on the left side if it is smaller than the root Node. Until empty BinarySearchTree. Prototype. Insert = function (key) {/ / create a key to insert the var newNode = new Node (key) / / determines whether to have a root Node, if not, If (this.root == null) {this.root = newNode} else {this.insertNode(this.root, NewNode)}} / / recursive function BinarySearchTree. Prototype. InsertNode = function (node, If (newNode.key > node.key) {// If (newNode.key > node.key) {// If (newNode.key > node.key) { If (node.right == null) {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) else {// If (node.right == null) InsertNode (node.right, If (node.left == null) {node.left = newNode} else {this.insertNode(node.left, newNode) } } }Copy the code

I’m not going to test it, but I’m going to test it with the traversal

PreOrderTraverse: Traverse all nodes by preordering traverse

If you understand one of them, you’ll almost understand the rest of the traversals

Principle: First access the root node, then access its left subtree, During a visit to right subtree BinarySearchTree. Prototype. PreOrderTraverse = function (handler) {/ / starting from the root node traversal this.preOrderTraverseNode(this.root, Handler)} / / BinarySearchTree sequence traversal recursive functions. The first prototype. PreOrderTraverseNode = function (node, handler) {if (node! Handler (node.key) {// Because it is traversal, so to see the result, use a function to process, add the passed node to the string // If there is a left node, execute our traversal function, add the node to the string, Until the left node is empty this. PreOrderTraverseNode (node) left, handler) / / if the last one left node to a leaf node, it in judging whether there is any right node / / if you have, will continue to perform recursive functions. / / if not, then the current node was finished last recursive calls, begin to determine the node of a recursive function enclosing preOrderTraverseNode (node. Right, handler)}}Copy the code

InOrderTraverse: Traverse all nodes through mid-order (ascending) traverse

It’s just changing the order of the call, and so is the post-order traversal

First access the left subtree, then access the root node, then access the right subtree, sort the tree if it is a number, Is small to large order BinarySearchTree. Prototype. InOrderTraverse = function (handler) {enclosing inOrderTraverseNode (enclosing root, Handler) // why this.root, Because only starting from the root node into} / / sequence traversal recursive function BinarySearchTree. Prototype. InOrderTraverseNode = function (node, handler) {if (node! = null) {/ / starting from the root node to enter, if he has left nodes, will be ongoing recursion, would have been the most left leaf node traversal to / / to the leftmost node leaves, just to add the node to the end of the string, in the judgment on whether there is a right node / / not returned to a function, the function of the left node determine ends, Add the current node to the string, to the right of the judgment //.... // If you enter a new branch, there is a left node, there is a recursive call, all functions come to the left leaf node. // You can view the left side of the root node as a function judgment of the left node. InOrderTraverseNode (node. Left, handler) Handler (node. Key) this.inOrderTraversenode (node. Right, handler)}}Copy the code

PostOrderTraverse: Traverse all nodes through the sequence

I won’t comment on it here

Principle: Access the left subtree first, before accessing the right subtree, During a visit to the root node BinarySearchTree. Prototype. PostOrderTraverse = function (handler) {enclosing postOrderTraverseNode (enclosing root, handler) } BinarySearchTree.prototype.postOrderTraverseNode = function (node, handler) { if (node ! < span style = "box-sizing: border-box! Important; Not said this. PostOrderTraverseNode (node. Left, handler) enclosing postOrderTraverseNode (node. Right, handler) handler(node.key) } }Copy the code

Min: Returns the smallest value key in the tree

There’s nothing to say about that. It’s what you think

BinarySearchTree. Prototype. Min = function () {var node = this. Root / / access to the root node / / var key = null to create a key to return value / / in turn to the right to search, Since node always has a value, it loops until node=null while (node! = null) { key = node.key node = node.left } return key }Copy the code

Max: Returns the largest value key in the tree

BinarySearchTree.prototype.max = function () { var node = this.root // var key = null while (node ! = null) { key = node.key node = node.right } return key }Copy the code

Search (key): Searches the tree for a key, returning true if the node exists

BinarySearchTree.prototype.search = function (key) { return this.searchNode(this.root, Key)} / / recursive BinarySearchTree prototype. SearchNode = function (node, key) {if (node = = = null) {/ / whether the root node is empty, Return false} if (key > node.key) {// After recursion, Return this.searchNode(node.right, key)} else if (key < node.key) {return this.searchNode(node.left, key) } else { return true } }Copy the code

test

Var BST = new BinarySearchTree() // Test insert BST. Insert (7) BST. Insert (66) BST. Bst.traverse (function (key) {res1 += key + "}) console.log(res1 Res2 = "BST. InOrderTraverse (function (key) {res2 += key +"}) console.log(res2) Bst.postordertraverse (function (key) {res2 += key + ' '}) console.log(res2) // size console.log(bst.min()) Console. log(bst.search(2)) console.log(bst.search(66))Copy the code

Tree diagram and result diagram

conclusion

In fact, there is another method, is remove, this method is a bit difficult, when the time comes to write a separate post

The guy who came up with the binary search tree, Cowhide. There’s no summary. I think the notes are my summary