preface

Tree data structure is widely used in the real world, such as family tree, enterprise functional structure, etc. It is a kind of nonlinear data structure widely used in the field of computer.

Binary tree is one of the most common types of tree data. This paper constructs and operates binary tree with JS syntax from the front end.

Basic concept

Looking at the figure above, the data structure of a binary tree is shown.

Each circle in the tree represents A node, where the node A at the root is called the root node

B and C are children of A. The number of child nodes is called degree, the degree of node A is 2, and the degree of node D is 1. Nodes with degree 0 are called leaf nodes, for example, H, E, F, and G in the figure all belong to leaf nodes

  • Depth of nodes: The total number of nodes on a unique path from the root node to the current node.
  • Node height: The total number of nodes along the path from the current node to the farthest leaf node.BThe height of the node is3.

Js construct binary tree

After the basic concept of binary tree is introduced, we will use JS to implement a binary tree.

A binary tree consists of nodes, each of which can be generated by a class (code below).

class Node { constructor(value){ this.value = value; this.left = this.right = null; }}Copy the code

This. value stores the value of the current node. This. left is the left node and this.right is the right node.

Now that the goal of defining a single node has been achieved, how do you combine these nodes to form a binary tree?

Suppose there is an array [0,1,2,3,4,5,6], convert the array into a binary tree (the order of data storage is shown below).

Observe the order of the data in the graph. The data is first fetched from left to right in the array, starting at level 0 of the binary tree, and then placed from top to bottom layer by layer. Each layer is placed from left to right.

The key of binary tree synthesis is that every node is generated, we need to know who is the parent of the node, and then we need to know whether the node belongs to the left or right of the parent node.

From the picture, we can conclude the following rules:

  • The index value of each layer element (the index in the array) is added1The logarithms are the same. For example, the first0Layer element0add1So let’s take the logarithm and round it down is equal to0.second layer element1and2all1And then we take the logarithm and the whole thing is equal to1. So the index value of each element in the arrayiUsing the formulaMath.floor(Math.log2(i+1))We get the number of levels in the binary tree.
  • The index of the first element at each level is equal to2thenThe power cut1, includingnIs equal to the number of layers the element is in.
  • The number of levels of the parent is equal to the number of levels of the current element minus1.
  • The index of each element minus the index of the first element in the layer divided by2Round down to find the parent’s position in its own layer. Such as element4Minus the3Divided by the2Take the whole for0. Then the parent element is at number 11The first layer0And5The parent of element no is computed in the same way1Layer of the first1A location.

Based on the above rules, each element can calculate its parent index by its own index value, and the binary tree is built naturally (code below).

class Btree { constructor(array){ this.transform(array); return this.root; } transform(array){ const list = []; Array.foreach ((item,index)=>{if(item == null){// Non-null processing list.push(null); return; } const node = new Node(item); list.push(node); if(! this.root){ this.root = node; return; Const layer = math.floor (math.log2 (index + 1)); Const first_index = math.pow (2,layer) -1; Const parent_position = math.floor ((index-first_index)/2); Const parent_layer = layer-1; Const parent_first_index = math.pow (2,parent_layer) -1; // Const parent_first_index = math.pow (2,parent_layer) -1; Const parent_index = parent_first_index + parent_position; Const parent_node = list[parent_index]; if(parent_node.left == null){ parent_node.left = node; }else{ parent_node.right = node; } }) list.length = 0; Node {value: 0, right: Node {value: 2, right: Node {value: 6, right: null, left: null}, left: Node { value: 5, right: null, left: null } }, left: Node { value: 1, right: Node { value: 4, right: null, left: Null}, left: Node {value: 3, right: null, left: null}}} */ console.log(new Btree([0,1,2,3,4,5,6])); module.exports = { Btree, Node };Copy the code

Maximum depth

Looking at the binary tree in the figure above, write the function maxDepth to find the maximum depth of the binary tree.

The maximum depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

For example, in the figure above, the number of nodes on the path 1-2-4-8 is 4, while the maximum number of nodes on other paths from root node to leaf node is only 3, so the maximum depth of the binary tree is 4.

It can be analyzed from the figure that the maximum depth of the binary tree must be equal to the larger value of the number of nodes forming a path between the root node and a leaf node of the left subtree or a leaf node of the right subtree.

For example, the maximum depth of root node 1 is equal to the greater depth of node 2 or node 3 plus one.

And the maximum depth of node 2 is equal to the greater depth of node 4 or node 5 plus one. The maximum depth of node 3 can be obtained similarly.

Finally, through layers of recursion, it must reach the lowest leaf node. The leaf node has no next level and has a maximum depth of 1, which can be the end condition for recursion.

const { Btree } = require("./Btree"); function maxDepth(node){ if(node == null){ return 0; } return Math.max(maxDepth(node.left),maxDepth(node.right)) + 1; } const root = new Btree([1,2,3,4,5,6,7,8]) console.log(maxDepth(root)); / / 4Copy the code

The diameter of a binary tree

The diameter length of a binary tree is the maximum of the path length of any two nodes. This path may or may not go through the root.

Observe the figure above, 8-4-2-1-3-6 and 8-4-2-1-3-7 are the two longest paths, and the path length is equal to the number of edges between nodes, so the diameter length of the binary tree is 5.

The number of DiameterOfBTree, which is DiameterOfBTree, has been calculated.

Calculating the diameter is actually calculating the extension of the maximum depth. According to the method of calculating the maximum depth, the maximum depth of root node 1 is equal to the greater value of the maximum depth of the left and right subtrees plus 1.

So if you add the maximum depth of the left subtree of root 1 and the maximum depth of the right subtree you get the diameter of the path through node 1.

The diameter length through the root node is not necessarily the maximum diameter length, for example, 6-4-2-5-8-9 is larger than the diameter through the root node.

1 / \ 2 3 / \ 4 5 / \ / \ 6 7 8 9/10Copy the code

Similarly, node 2 is the root node of the left subtree, and its diameter is equal to the maximum depth of its left subtree plus the maximum depth of its right subtree.

So you can define a global variable Max to store the maximum diameter length. In the process of recursive calculation of maximum depth, the length of each calculated diameter is compared with Max, and if the value is larger than Max, the value is assigned to Max. At the end of the recursion, Max is equal to the maximum diameter of the entire binary tree.

const { Btree } = require("./Btree"); function DiameterOfBTree(node){ let max = 0; (function maxDepth(node){ if(node == null){ return 0; } const maxLeftDepth = maxDepth(node.left); const maxRightDepth = maxDepth(node.right); const diameter = maxLeftDepth + maxRightDepth; if(diameter > max){ max = diameter; } return Math.max(maxLeftDepth,maxRightDepth) + 1; })(node); return max; } const root = new Btree([1,2,3,4,5,6,7,8]) console.log(DiameterOfBTree(root)); / / 5Copy the code

Balanced binary trees

The absolute value of the difference in height between the left and right subtrees of each node is no more than 1.

For example, the following binary tree is a balanced binary tree.

10 / \ 2 12 / \ 15Copy the code

The following binary trees are nonequilibrium binary trees.

          10
         /  \
        2    12 
       / \       
      1   5 
     / \ 
    11  13
Copy the code

Please write the function isBalanced to check whether the binary tree is a balanced binary tree.

The key condition to judge the balance is that the height difference between the left and right nodes in the same subtree cannot be greater than 1.

Therefore, the height difference between left and right subtrees can be solved recursively from the root node. As long as one height difference is greater than 1, the final result returned is false.

const { Btree } = require("./Btree"); function isBalanced(node){ let result = true; function handler(node){ if(! node){ return 0; } const left_height = handler(node.left) + 1; Const right_height = handler(node.right) + 1; // Right subtree height increment 1 if(! result){ return; } if(math.abs (left_height-right_height) > 1){// If (math.abs (left_height-right_height) > 1) } return Math.max(left_height,right_height); } handler(node); return result; } the console. The log (isBalanced (new Btree ([3,9,20, null, null, 15, 7]))); / / true on the console. The log (isBalanced (new Btree ([,2,2,3,3 1, null, null, 4, 4]))); // falseCopy the code

Symmetric binary tree

A tree is a symmetric binary tree if its left and right subtrees mirror each other.

For example, the following binary tree,2,2,3,4,4,3,5,6,7,8,8,7,6,5 [1] is symmetrical.

1 /\ 2 2 /\ / 3 4 4 3 /\ / / / / / 5 6 7 8 8 8 7 6 5Copy the code

Please write isSymmetric function to verify whether a binary tree isSymmetric.

By analyzing the structural characteristics of the symmetric binary tree, the values of the left and right child nodes under the root node 1 are equal.

The value of the left node of left subtree 2 is equal to the value of the right node of right subtree 2. The value of the right node of left subtree 2 is equal to the value of the left node of right subtree 2.

After the second layer is compared, the left node of left subtree 2 node and the right node of right subtree 2 node continue to be compared recursively according to the above process. Similarly, the right node of the left subtree 2 node and the left node of the right subtree 2 node are also compared recursively according to the above process.

Then the law of judging whether each layer is symmetrical is summarized as follows.

  • The two nodesAandBThe values are equal
  • AThe value of the left node of the node is equal toBThe value of the right node of the node,AThe value of the right node of the node is equal toBThe value of the left node of the node
Function isSymmetric(root){function hanlder(nodeA,nodeB){// Two nodes are asymmetric if((nodeA == null && nodeB! = null) || (nodeA ! = null && nodeB == null)){ return false; If (nodeA == null && nodeB == null){return true; } // The value of two nodes is not equal is asymmetric if(nodea. value! = nodeB.value){ return false; } return hanlder(nodeA.left,nodeB.right) && hanlder(nodeA.right,nodeB.left); } return hanlder(root.left,root.right); } const tree = new Btree (,2,2,3,4,4,3,5,6,7,8,8,7,6,5 [1]); console.log(isSymmetric(tree)); // trueCopy the code

Binary search tree

The binary search tree is defined as follows:

  • The left subtree of a node contains only numbers less than the current node
  • The right subtree of a node only contains numbers greater than the current node
  • All left and right subtrees must themselves also be binary search trees

For example, the following data structure is a binary search tree. The value of the current node is less than the value of the right node and greater than the value of the left node. Subtrees follow the same pattern.

10 / \ 2 12 / \ / 1 5 11 13Copy the code

Js build binary search tree

The idea of building a binary search tree is very simple. Each time a new node is inserted, starting from the root node, values greater than the root node are placed on the right and less than the left. The process continues recursively until a new node is inserted when the child node is empty.

const { Node } = require("./Btree"); class Bst { constructor(list = []){ this.root = new Node(list.shift()); list.forEach((item)=>{ this.add(new Node(item)); }) return this.root; } add(node){ if(! this.root){ this.root = node; return; } let current = this.root; let parent; let direction; while(current){ parent = current; If (node.value > current. Value){// Insert current = current. direction = "RIGHT"; }else if(node.value < current-value){current = current-.left; direction = "LEFT"; }else{direction = null; break; } } if(direction == "LEFT"){ parent.left = node; }else if(direction == "RIGHT"){ parent.right = node; } } } /* Node { value: 6, right: Node { value: 7, right: Node { value: 8, right: null, left: null }, left: null }, left: Node { value: 2, right: Node { value: 3, right: null, left: null }, left: Null}} */ console.log(new Bst([6,2,3,7,8]); module.exports = { Bst }Copy the code

Enhanced comparison method

If the data structure is in the form [{name:” Zhang SAN “,score:90},{name:” Li Si “,score:100},{name:” Wang Wu “,score:80}], then how to use binary search tree storage?

The solution is simple, just add a compare method to the original, so that the size of the comparison method can be customized by external functions (code below).

class Bstv2 { compare(valueA,valueB){ if(this.compareFun){ return this.compareFun(valueA,valueB); } return valueA - valueB; } constructor(list = [],compareFun){ this.compareFun = compareFun; this.root = new Node(list.shift()); list.forEach((item)=>{ this.add(new Node(item)); }) return this.root; } add(node){ if(! this.root){ this.root = node; return; } let current = this.root; let parent; let direction; while(current){ parent = current; If (this.pare (node.value,current.value)){this.pare (node.value,current.value); direction = "RIGHT"; This.pare (this.value,node.value)){this.pare (this.value,node.value); direction = "LEFT"; }else{direction = null; break; } } if(direction == "LEFT"){ parent.left = node; }else if(direction == "RIGHT"){ parent.right = node; }}} /* Node {value: {name: 'score ', score: 90}, right: Node {value: {name:' score ', score: 100}, right: null, left: Null}, left: Node {value: {name: 'score ', score: 80}, right: null, left: null } } */ console.log(new Function (valueA,valueB){return valuea.score > function(valueA,valueB){return valuea.score > valueB.score; }));Copy the code

Binary search tree sorting

Observe the following binary tree structure, large values on the right, small values on the left, such a data structure has been binary processing.

10 / \ 2 12 / \ / 1 5 11 13Copy the code

Binary search tree has an advantage in the query and sorting of big data because of the binary data processing during the construction.

In order to learn the query and sort of binary search tree, it is necessary to understand the four common traversal methods.

  • Sequential traversal. First the root node is accessed, then the left subtree, then the right subtree.
  • The left subtree is accessed first, then the root node, then the right subtree.
  • Sequential traversal: first the left subtree, then the right subtree, then the root node.
  • Sequential traversal. Top to bottom, layer by layer.

Take the binary tree above. A sequential traversal visits node 10, then left node 2, and then right node 12.

The above process is recursively executed while accessing left node 2. Access node 2, then left node 1, and then right node 5. After accessing the left subtree, access the right subtree. Similarly, node 12 performs the above process recursively.

The sequence traversal process: node 10 is visited first, then layer 2 and 12, then layer 3 1, 5, 11 and 13.

The following code demonstrates the four traversal modes.

const { Bst } = require("./Bst"); Const root = new Bst([10,2,12,1,5,11,13]); Function preorderTraversal(node,callback){if(! node){ return; } callback(node); preorderTraversal(node.left,callback); preorderTraversal(node.right,callback); } console.log(preorderTraversal(root,function(node){ console.log(node.value); }); Sequence traversal in / / / * * can be seen from the results, the sequence traversal is equal to the smallest to the result of the result. */ function midTraversal(node,callback){if(! node){ return; } midTraversal(node.left,callback); callback(node); midTraversal(node.right,callback); } console.log(midTraversal(root,function(node){ console.log(node.value); // 12 5 10 11 12 13}); Function postorderTraversal(node,callback){if(! node){ return; } postorderTraversal(node.left,callback); postorderTraversal(node.right,callback); callback(node); } console.log(postorderTraversal(root,function(node){ console.log(node.value); // 1 5 2 11 13 12 10}); Function postorderTraversal(node,callback){const array = [node]; for(let i = 0; i<array.length; i++){ const item = array[i]; if(! item){ return; } callback(item); array.push(item.left); array.push(item.right); } } console.log(postorderTraversal(root,function(node){ console.log(node.value); });Copy the code

Binary search tree query

Query an element from a binary search tree, return true if found, false if not found.

const { Bst } = require("./Bst"); Const root = new Bst([10,2,12,1,5,11,13]); function search(node,value){ if(! node){ return false; } else if(node.value == value){ return true; } else if(value > node.value){ return search(node.right,value); }else{ return search(node.left,value); } } console.log(search(root,12)); // true console.log(search(root,100)); // falseCopy the code

flip

The similar structure of binary search tree is as follows. Would you write the function reverse to reverse it?

10 / \ 2 12 / \ / 1 5 11 13Copy the code

The flipped binary tree structure is as follows:

1/2/2/3Copy the code

By using the traversal method learned earlier, the rollover function is easily realized.

const { Bst } = require("./Bst"); function reverse(root){ function preorderTraversal(node){ if(! node){ return; } const tmp = node.left; // Switch between left and right nodes node.left = node.right; node.right = tmp; preorderTraversal(node.left); preorderTraversal(node.right); } preorderTraversal(root); return root; } const root = new Bst([10,2,12,1,5,11,13]); /* Node { value: 10, right: Node { value: 2, right: Node { value: 1, right: null, left: null }, left: Node { value: 5, right: null, left: null } }, left: Node { value: 12, right: Node { value: 11, right: null, left: null }, left: Node { value: 13, right: null, left: null } } } */ console.log(reverse(root));Copy the code

Verify the binary search tree

Is a tree a binary search tree?

If the value of a binary search tree is greater than the value of the left node and less than the value of the right node, false is returned.

const { Bst } = require("./Bst"); function isBst(node){ if(! node){ return true; } if( (node.right && node.value >= node.right.value) || (node.left && node.value <= node.left.value)){ return false; } return isBst(node.left) && isBst(node.right); } const root = new Bst([10,2,12,1,5,11,13]); console.log(isBst(root)); // true console.log(isBst(reverse(root))); // falseCopy the code