Basic concepts of tree structure
A tree structure consists of a series of nodes that have parent-child relationships. Each node has a parent (except for the first node at the top) and zero or more child nodes, which store data internally.
Element nodes are like subscripts in an array, and the data stored inside the node is like the values corresponding to the array subscripts.
The node at the top of the uppermost tree is called the root node (11) and has no parent. Each element in the tree is called a node, and nodes are divided into inner nodes and outer nodes.
Nodes with at least one child node are called internal nodes (7, 5, 9, 15, 13, and 20 are internal nodes). Nodes without child elements are called external nodes or leaf nodes (like leaves of a tree,3, 6, 8, 10, 12, 14, 18, and 25 are leaf nodes).
A node can have ancestors and descendants. The ancestors of a node (in addition to the root node) include the parent node, the grandfather node, the great-grandfather node, and so on. The descendants of a node include children, grandchildren, and great-grandchildren. For example, the ancestors of node 5 are nodes 7 and 11, and the descendants are nodes 3 and 6.
Subtree, a subtree consisting of a node and all of its descendants (i.e., the range from that node to all of its leaf nodes). For example, nodes 13, 12, and 14 form a subtree of the tree in the figure above. .
One attribute of a node is its depth, which depends on the number of ancestor nodes, not the node itself. It is as deep as there are ancestor nodes above it. For example, node 3 has three ancestor nodes (5, 7, and 11) and has a depth of 3.
The height of the tree depends on the maximum depth of all nodes. A tree can also be broken down into layers. The root node is at layer 0, the children of the root node are at layer 1, and so on. The tree in the figure above has a height of 3 (the maximum height is indicated in the figure – level 3).
Binary tree
Each node in a binary tree can have at most two child nodes: one on the left and one on the right. (Note: binary trees do not enforce that the left child is smaller than the parent and the right child is greater than or equal to the parent. Only binary search trees store values smaller than the parent on the left child and larger on the right. This definition helps us write more efficient algorithms for inserting, finding, and removing nodes in a tree.
A binary search tree (BST) is a type of binary tree, but only allows the left child node to store values smaller than the parent node, and the right child node to store values larger than the parent node.
Technical realization of tree structure
Create a Node class to represent each Node in the binary search tree.
As with linked lists, we will represent relationships between nodes (called edges in tree-related terminology) by Pointers (references).
In a bidirectional linked list, each node contains two Pointers, one to the next node and one to the previous node.
For trees, use the same method (also using two Pointers), but one points to the left child and the other to the right. Therefore, a Node class is declared to represent each Node in the tree. One small detail worth noting is that instead of referring to the nodes themselves as nodes or items in the previous section, we will refer to them as keys. A key is a name for a node in tree-related terms.
Here are the methods that will be implemented in the BinarySearchTree class.
Insert (key) : Inserts a new key into the tree.
Search (key) : Finds a key in the tree. Returns true if the node exists; If it does not exist, return false.
InOrderTraverse () : Traverse all nodes with mid-order traversal.
PreOrderTraverse () : traverse all nodes with preOrderTraverse.
PostOrderTraverse () : Traverse all nodes with post-traversal.
Min () : Returns the smallest value/key in the tree.
Max () : Returns the largest value/key in the tree.
Remove (key) : Removes a key from the tree.
The maximum and minimum search values are shown below:
Binary search tree code
// Each place in the tree where data is stored is called an element node, so create a class for that node
class Node{
constructor(key){ // The key in the tree is not like the index in the stack or queue. The key in the tree directly corresponds to the data value stored by the node
this.key = key // Storage node value
this.left = null // Index points to the left child node, like a bidirectional list. Lists are up and down structures (pointer fields point up and down) and trees are left and right structures (pointer fields point left and right).
this.right = null // Index to the right child node}}// Binary search tree class
class BinarySearchTree{
constructor(){
this.root = null // The root node of the binary tree. The default value is null
}
insert(key){ // Insert new values into the binary tree
if(!this.root){ // If the root node has no value, it is inserted into the root node of the binary tree
this.root = new Node(key)
}else{ // If the root node already has a value, make a judgment and compare the value of the inserted child node with the value of the parent node to determine the left child node or the right child node
// Calls a method that inserts values into a node
this.insertNode(this.root,key) // this.root because every time a new value is inserted, the root node is used to compare the size and insert the value}}insertNode(node,key){ // Insert a value into a node. Node represents the parent node, and key represents the value of the child node. The value of the child node is compared with the value of the parent node
// The reason for this is to be able to call recursively when there is already a lot of data
if(key < node.key){ // If the value to be inserted is smaller than the value of the parent node, insert the left side
If there is already a child node to the left of the parent node (because it is not possible to insert children of the root node every time, in case there are many layers), then determine
if(node.left){ // There are already children to the left of the parent node, so the value to be inserted will be the children of that child node (not sure how many layers, so recurse).
this.insertNode(node.left,key) // Recursively calls a method to insert values into a node, this time comparing the value of the left child node to the value to be inserted
}else{ // If there are no children to the left of the parent node, insert the child node directly into the parent node
node.left = new Node(key)
}
}else{ // If greater than or equal to is inserted on the right side, the right child node is also evaluated recursively
if(node.right){ // There are already children to the right of the parent node, so the value to be inserted will be the children of that child node (not sure how many layers, so recurse).
this.insertNode(node.right,key) // Recursively calls a method to insert values into a node, this time comparing the value of the right child node to the value to be inserted
}else{ // If there are no children to the right of the parent node, insert them as children of the parent node
node.right = new Node(key)
}
}
}
min(){ // Query the minimum value of the entire binary tree, also requires a recursive method, because there is no way to know which node is the minimum value
return this.minNode(this.root) // Returns the return value of the function method that recursively evaluates to find the minimum value starting at the root node
}
// The minNode method is the same as the minNode method. The minNode method is the same as the minNode method.
minNode(node){ // Determine recursively how to find the minimum value starting from a specified node. Node represents the node passed in
let current = node // Save the current node passed each time in a variable
while(current && current.left){ // When the current node has a value and the left child node of the current node also has a value, there is a smaller value
current = current.left // Change the left child node to the current node to continue the loop comparison
}
// If there are no children on the left, the current node is the minimum node
return current
}
max(){ // Query the maximum value of the entire binary tree, also requires a recursive method, because there is no way to know which node is the minimum value
return this.maxNode(this.root) // Returns the return value of the function method that recursively evaluates to find the minimum value starting at the root node
}
// The Max method is different from the maxNode method. The Max method looks for the maximum value of the entire tree, and the Max method looks for the maximum value of the tree from a node down.
maxNode(node){ // Determine recursively how to find the maximum value starting from a specified node. Node represents the node passed in
let current = node // Save the current node passed each time in a variable
while(current && current.right){ // If the current node has a value and the child nodes to the right of the current node have a value, there is a larger value
current = current.right // Change the right child node to the current node and continue the loop comparison
}
If there is no child node on the right, the current node is the node with the maximum value
return current
}
// middle order traversal
inOrderTraverse(cb){ // Receives a callback function that iterates through the sort order
this.inOrderTraverseNode(this.root,cb) // Start from the root node to iterate through the sort
}
inOrderTraverseNode(node,cb){ // Order traversal recursive method
if(node){ // Do traversal only when the node exists
this.inOrderTraverseNode(node.left,cb) // If there are children to the left of the node, it enters recursion
// Go all the way to the left child. If there are left children below, this layer will enter the recursive method again, but will not go to the next line cb(),
// Because you are currently stuck in this layer and entering this layer of recursion (this is why cb is not executed immediately), if there are left child nodes, repeat the operation again
// The cb function of the current layer is performed until there is no next left child node, and then the cb() operation of the previous layer is performed after the recursion of the current layer
cb(node.key) // Until the node has no left child nodes, the value of the node traversed by the current layer is put into the callback function
this.inOrderTraverseNode(node.right,cb) Similarly, we still need to determine whether the right child node of this node exists. If there is a right child node, then the current layer enters the recursion to determine whether there are left children below the right child node}}// order traversal first
preOrderTraverse(cb){ // Receives a callback that iterates through the structure of the data
this.preOrderTraverseNode(this.root,cb) // Start with the root node
}
preOrderTraverseNode(node,cb){ // First traversal the recursive method
if(node){ // Do traversal only when the node exists
cb(node.key) // Put the iterated value into the callback function for operation
this.preOrderTraverseNode(node.left,cb) // If there are children to the left of the node, it enters recursion
/ / to the left child nodes to find, if there are on the left side of the child nodes, this layer will enter the recursive method, but not the implementation of the current layer one line of code. This preOrderTraverseNode,
// Because you are currently stuck at this level and entering this level of recursion (this is why the next line of code will not be executed immediately), if there are left child nodes, repeat the operation again
/ / until no one on the left side of the child nodes can perform under the current layer to the next line of code. This preOrderTraverseNode, if the conditions in the next line of code does not meet the recursion, recursion is out of the current layer, return to a layer, continue to implement a layer on the next line of code
this.preOrderTraverseNode(node.right,cb) // Similarly, it is still necessary to determine whether the right child node of this node exists. If there is a right child node, the current layer enters recursion}}// after the sequence traversal
postOrderTraverse(cb){ // Receives a callback function, traversed sequentially
this.postOrderTraverseNode(this.root,cb) // Sort from the root node
}
postOrderTraverseNode(node,cb){ // the post-order traversal recursive method
if(node){ // Do traversal only when the node exists
this.postOrderTraverseNode(node.left,cb) // If there are children to the left of the node, it enters recursion
/ / to the left child nodes to find, if there are on the left side of the child nodes, this layer will enter the recursive method, but not the implementation of the current layer one line of code. This preOrderTraverseNode,
// Because you are currently stuck in this level and entering this level of recursion (this is why the next line is not executed immediately), if there are left child nodes, repeat the operation again
/ / until no one on the left side of the child nodes can perform under the current layer to the next line of code. This preOrderTraverseNode, if the conditions in the next line of code does not meet the recursion, recursion is out of the current layer, return to a layer, continue to implement a layer on the next line of code
this.postOrderTraverseNode(node.right,cb) // Similarly, it is still necessary to determine whether the right child node of this node exists. If there is a right child node, the current layer enters recursion
cb(node.key) // Until the above two lines of code do not continue to the next level of recursion, the current level of the node traversed by the value of the callback function to operate}}// Search function
searchKey(key){
return this.searchNode(this.root,key)
}
searchNode(node,key){ // Recursive method
// Check if there is anything inside the tree
if(node){ // There must be nodes in the tree to search
// Determine the size of the value and determine which side to search
if(key < node.key){ // If the value passed is smaller than the value of the current node, continue the search for the left child node
return this.searchNode(node.left,key)
}else if(key > node.key){ // If the value passed is greater than the value of the current node, continue the search for the right child node
return this.searchNode(node.right,key)
}else{ // It is neither greater than nor less than
return true}}else{ // If the node does not exist, do not search
return false}}// Delete function
removeKey(key){
this.root = this.removeNode(this.root,key)
}
removeNode(node,key){
if(node){ // The tree can be deleted only if there are nodes in it
if(key < node.key){ // Search from the left
node.left = this.removeNode(node.left,key)
return node // Return the spliced node
}else if(key > node.key){ // Search from the right
node.right = this.removeNode(node.right,key)
return node // Return the spliced node
}else{ // The object to delete is found
// In the first case, the node to be deleted has children on both the left and right sides
if(node.left && node.right){
console.log("Replace the former node",node)
console.log("Right before replacement child node",node.right)
let target = this.minNode(node.right) // Find the smallest child node of the child node on the right of the node to be deleted, that is, the smallest grandson node
node.key = target.key // The smallest grandchild node is replaced by the deleted node
node.right = this.removeNode(node.right,key) // Delete the smallest grandchild node from the original grandchild node
console.log("Node after replacement",node)
console.log("Right child node after replacement",node.right)
return node
}
// In the second case, there are children to the left or right of the node to be deleted
if(node.left || node.right){
if(node.left){ // If there are children on the left of the node to be deleted, the child on the left replaces the deleted node
node = node.left
}
if(node.right){ / / in the same way
node = node.right
}
return node // Return the replaced node
}
// Third case: the node to be deleted is a leaf node
node = null
return node
}
}else{
return null}}// Modify the function
updateKey(key,key1){
return this.updateNode(this.root,key,kye1)
}
updateNode(node,key,key1){ // Recursive method
// Check if there is anything inside the tree
if(node){ // There must be nodes in the tree to search
// Determine the size of the value and determine which side to search
if(key < node.key){ // If the value passed is smaller than the value of the current node, continue the search for the left child node
return this.updateNode(node.left,key,key1)
}else if(key > node.key){ // If the value passed is greater than the value of the current node, continue the search for the right child node
return this.updateNode(node.right,key,key1)
}else{ // It is neither greater than nor less than
node.key = key1
return true}}else{ // If the node does not exist, do not search
return false}}}let treeData = new BinarySearchTree() // instantiate the object
treeData.insert(10)
treeData.insert(4)
treeData.insert(16)
treeData.insert(3)
treeData.insert(8)
treeData.insert(13)
treeData.insert(20)
treeData.insert(11)
treeData.insert(1)
treeData.insert(21)
treeData.insert(3241)
treeData.insert(10)
treeData.insert(8)
treeData.insert(4)
treeData.insert(3)
treeData.insert(90)
treeData.insert(19)
treeData.insert(14)
Copy the codeSequence traversal, sequence traversal, sequence traversal after detailed explanation
Tree structure of the technical implementation of the first, middle, after order traversal (interviews may require handwritten code!! The code is identical except that the cb callback is located in a different position.
Walking through a tree is the process of visiting each node of the tree and performing some kind of operation on them.
There are three ways to access all nodes of the tree: middle-order traversal (sort), pre-order traversal (similar to viewing the document structure of the entire folder), and post-order traversal (similar to querying the size of the entire document)
1. Sequential traversal is a traversal mode in which more than one row accesses all nodes of BST sequentially, that is, all nodes are accessed sequentially from the smallest to the largest. One application of middle-order traversal is to sort trees.
To traverse a tree by middle-order traversal method, first check whether the node passed in the form of parameter is null (this is the judgment condition of stopping recursion to continue, namely the baseline condition of recursive algorithm). Then, the same function is recursively called to access the left child node first. Some operations such as callback are performed on the root node, and finally the right child node is accessed. The detailed process is shown in the figure below:
2. Sequential traversal accesses each node in the order that the ancestor node takes precedence over the descendant node. One application of preemptive traversal is to print a structured document. Pre-ordered traversal differs from middle-ordered traversal in that pre-ordered traversal visits the node itself first, then its left child, and finally its right child. As shown below:
3. After traversal, the descendant nodes of a node are accessed first, and then the node itself is accessed. One application scenario for back-order traversal is to calculate the space occupied by all files in a directory and its subdirectories. A back-order traversal visits the left child of the node first, then the right child of the node, and finally the parent node itself. As shown below:
Delete node diagram
There are three cases when a node is deleted:
1. If the node to be deleted happens to be a leaf node, it can be deleted directly, as shown below:
2. Delete nodes below the left or the right to exist a child node, will exist below that replace the deleted node node, as shown in the figure below, 3 5 below the left child node is deleted, just need to replace to the node node 3 5 position, after the node is replaced naturally, is to be deleted
3. There are child nodes on the left and right of the deleted node. Find the smallest node in the right subtree below the deleted node and replace the deleted node. As shown in the figure below, we want to delete node 15. Below node 15, there is a subtree starting from node 13 on the left and a subtree starting from node 20 on the right. At this point, we only need to find the smallest node 18 in the right subtree starting from node 20 (why is the smallest node of the right subtree? Because the smallest node in the right subtree must be greater than or equal to all the nodes in the left subtree, and must be smaller than all the nodes in the right subtree. Of course, you can also choose to replace the deleted node with the largest node in the left subtree, which is the same principle), so you just need to remove node 18 from its original position and replace it with node 15, which completes the deletion of node 3.
