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…