This is the 8th day of my participation in the August Text Challenge.More challenges in August
First, the introduction of trees
 Tree: n
(n >= 0)
A finite set of nodes  For any nonempty tree
(n > 0)
, with the following properties: The tree has a special node called **” root “**
 The remaining nodes can be divided into M
(m > 0)
Two finite sets that do not intersect each otherT1, T2... , Tm,
Where each set is itself a tree, called the **” subtree “of the original tree **
The properties of trees are many…
 Degree of nodes: the number of nodes in the tree
 1. A node of degree 0 (also called a leaf node).
 Node hierarchy: specify that the root node is at layer 1, and the number of layers of any other node is the number of layers of its parent node plus 1
Binary, binary tree
Properties of binary trees

The maximum number of nodes at the ith level of a binary tree is: 2^(i1), I >=1
For example, the first layer (root node) is 1; The second layer has a maximum of 2 nodes

The maximum number of nodes in a binary tree of depth k is: 2^k1, k>=1

For any nonempty binary tree T, if n0 represents the number of leaf nodes (degree 0) and n2 represents the number of nonleaf nodes with degree 2, then the relation n0 = n2 + 1 is satisfied
A. Complete binary tree

Except for the last layer of the binary tree, the number of nodes in other layers reaches the maximum

And the last layer reaches the continuous existence of leaf nodes from left to right, only missing several nodes on the right

In the graph below, from left to right, E has a right child but D doesn’t, so it’s not a complete binary tree. If you add a right child to D, then it’s a complete binary tree
B. Perfect binary tree (full binary tree)
 In a binary tree, a full binary tree is formed when each node has 2 child nodes except the leaf node at the lowest level
Binary trees can be stored as arrays or linked lists, but we usually use linked lists. Because if you use an array if the binary tree is not a full binary tree, it’s going to waste a lot of space.
Three, binary search tree
 Binary search tree is a binary tree, can be empty; If it is not empty, it satisfies the following properties:
 All keys of a nonempty left subtree are less than the keys of its root node
 All keys of a nonempty right subtree are greater than those of its root node
 The left and right subtrees themselves are binary search trees
Binary search tree initialization

First, the binary search tree has a root node. Initialization makes the root node point to null. this.root = null;

Secondly, each node of the binary search tree contains three elements, left child node, right child node and key value. In the initial state, the pointer is null
function Node() { this.key = key; this.left = null; this.right = null; } Copy the code
Four, binary search tree common methods
insert(key):
Inserts a new key into the treesearch(key):
Finds a key in the tree, returns true if the node exists; If not, return falseinOrderTraverse:
All nodes are traversed by middleorder traversalpreOrderTraverse:
All nodes are traversed by sequential traversalpostOrderTraverse:
All nodes are traversed through the sequential traversal modemin:
Returns the smallest value/key in the treemax:
Returns the largest value/key in the treeremove(key):
Removes a key from the tree
1. insert
methods

Create a node based on the key

Determine whether the root node has a value; If the root node is null, go to the next step
BinarySearchTree.prototype.insert = function (key) { var newNode = new Node(key); if (this.root == null) { this.root = newNode; } else { this.insertNode(this.root, newNode); }}Copy the code

In search tree insertion operation, if the value of the insertion is greater than the root node, then the node should be inserted into the right child node of the root node. If the root node already has a right child, you should continue to compare the value of the node to the right child. The process is essentially a nesting doll until the left or right node is empty, so this is done recursively, another function is used to insert the node.
BinarySearchTree.prototype.insertNode = function (node, newNode) { if (newNode.key < node.key) { if (node.left == null) { node.left = newNode; } else { this.insertNode(node.left, newNode); }}else { if (node.right == null) { node.right = newNode; } else { this.insertNode(node.right, newNode); }}}Copy the code
2. Traverse the binary search tree
Because the structure of the tree is special, we often use recursive method to achieve the traversal of nodes.
A. Sequential traversal
 Accessing the root node
 The left subtree is traversed first, and the right subtree is traversed first
BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
if(node ! =null) {
handler(node.key);
this.preOrderTraversalNode(node.left, handler);
// 3. Process the right child of the passed node
this.preOrderTraversalNode(node.right, handler); }}//
var resultString = ' '
tree.preOrderTraversal(function (key) {
resultString += key + ' ';
})
Copy the code
Handler is a callback function that handles the node so we can see the result of the loop; In preemptive traversal, we first traverse all the left child nodes, and then process the right child nodes that pass through the node. Like this one:
So the recursive idea here is a little bit more complicated, it’s a nesting of functions, and it jumps out one by one at the end of the walk, and it takes a little bit of time to understand.
After traversing the left node of 7 to 5, iterate through 3, which is the leaf node, and continue through 6 (node 5 at this point). After traversing the left node of 5, iterate through the right child node of 7.
B. Middleorder traversal
 The order traverses its left subtree
 Accessing the root node
 Middle order traverses the right subtree
if(node ! =null) {
this.inOrderTraversalNode(node.left, handler);
handler(node.key);
this.inOrderTraversalNode(node.right, handler);
}
Copy the code
C. Postorder traversal
 The left subtree is traversed, and the right subtree is traversed
 Accessing the root node
if(node ! =null) {
this.inOrderTraversalNode(node.left, handler);
this.inOrderTraversalNode(node.right, handler);
handler(node.key);
}
Copy the code
After understanding preorder traversal, middle order traversal and post order traversal are implemented in a recursive way, the difference is when to process nodes.
3. Maximum & minimum
Maxima and minima are easy to find in numbers. The leftmost child node (bottom left) is the minimum; The rightmost child node (bottom right) is the maximum. Here is a demonstration of finding the maximum value.
 Get the root node
 Search to the right until the node is null
BinarySearchTree.prototype.max = function () {
var node = this.root;
var key = null;
while(node ! =null) {
key = node.key
node = node.right
}
return node.key
}
Copy the code
Keep searching for the right node until the value of the right node is empty and return the key value of the node.
4. Search for specific values
This method can be implemented recursively or through a loop for searching

Recursion; Key == key, returns true, or false if it cannot be found after these steps.
BinarySearchTree.prototype.searchNode = function (node, key) { if (node == null) { return false; } if (node.key > key) { return this.searchNode(node.left, key); } else if (node.key < key) { return this.searchNode(node.right, key); } else { return true; } return false; } Copy the code

The loop retrieves the root node and then loops for the key
A little bit easier to understand if you’re doing a loop, you’re doing a keyvalue comparison, and you’re going to go to the left subtree or the right subtree until you find the target value.
var node = this.root; while(node ! =null) { if (node.key > key) { node = node.left; } else if (node.key < key) { node = node.right; } else { return true; }}return false; Copy the code
Deleting is the most complicated, so save it for the next article! I can’t go to school today aaa… Teacher CodeWhy really did a great job!