Tree data structure
A tree is a hierarchical abstract model. A common example in real life is a family tree or a diagram of a company’s structure. The node at the top of the tree is called the root node. He has no parent node, every element in the tree is called a node,
Nodes are divided into internal nodes and external nodes nodes that have at least one child node are called internal nodes. Nodes with no child elements are called outer nodes or 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 descendants of a node include child nodes, grandchildren, and great-grandchildren.
Subtree: A subtree consists of a node and its descendants.
The attribute of a node is depth, and the depth of a node depends on the number of its ancestor nodes.
The height of a tree depends on the maximum value of all nodes. A tree can also be broken down into levels. The root node is at layer 0, and its children are at layer 1. And so on.
Binary trees and binary search trees
A node in a binary tree can have at most two child nodes, a left child node and a right self node.
A binary search tree (BST) is a type of binary tree, but only allows you to store smaller values on the left node and larger values on the right node.
Create a BinarySearchTree class
export class Node{
consutructor(key){
this.key=key
this.left=null
this.right=null
}
}
Copy the code
As with linked lists, we will represent relationships between nodes through pointer 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, but one points to the left node and one to the right node. Therefore, a Node class is declared to represent each Node of the tree, with the key being the name for the Node in tree-related terms.
Export default class BinarySearchTree{consutructor(compareFn=defCompare){this.compareFn=compareFn// Compares node values this.root=null } }Copy the code
Root has the same schema as head in the linked list
Insert (key): Inserts a new key into the tree
Search (key): Finds a key in the tree. Returns true if the node exists, false otherwise
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 (): Removes a key from the tree
Inserts a key into the binary search tree
insert(key){
if(this.root=null){
this.root=new Node(key)
}else{
this.insertNode(this.root,key)
}
}
Copy the code
Inserting a node into the tree takes three steps
The first step is to verify that the insert operation is a special case. In the special case of a binary search tree, is the tree Node that we’re trying to insert the first Node, yes, what we’re going to do is create an instance of the Node class and assign it to the root property so root points to this new Node. Since we only need to pass the Node key we want to insert into the tree to the constructor, its left and right Pointers are automatically set to NULL by the constructor.
The second step is to add the node somewhere other than the root node. We need an auxiliary method
insertNode(node,key){ if(this.compareFn(key,node.key)===CompoareLESS_THAN){ if(node.left==null){ node.left=new Node(key) }else{ this.insertNode(node.left,key) } }else{ if(node.right==null){ node.right=new Node(key) }else{ this.insertNode(node.right,key) } } }Copy the code
The insertNode method will help us find the correct location where the new node should be inserted, implementing the steps
If the tree is not empty, you need to find where to insert the new node. So when you call the insertNode method, you pass in arguments to the root node of the tree and the node to insert
If the key of the new node is smaller than the key of the current node (now the current node is the root node) then the left child node of the current node needs to be checked. Note that since the key may be an object of load rather than a number, we use the compareFn function passed in to the binary search constructor to compare the values. If he has no left child, he inserts a new node on the left, and if he has a left child, he continues to find the next level of the tree using the recursive insertNode method. In this case, the next node to be compared will be the left child of the current node (left nodal tree)
To be continued…