A Tree (Tree)

The definition of the tree

A tree is made up of roots and several subtrees. A tree is made up of a set and a relationship defined on that set. The elements of the set are called nodes of the tree, and the relationships defined are called parent-child relationships. The parent-child relationship establishes a hierarchy between nodes in the tree. In this hierarchy, one node has a special status, which is called the root of the tree, or root.

Tree: a finite set of n(n>= 0) nodes.

When n = 0, it’s called an empty tree
Degree of node: number of subtrees of node >= 1
Degree of tree: The maximum degree of any node in the tree
Leaf node: node with degree 0
Path and path length: the number of line segments between nodes, for example, a-B-C is 2
Hierarchy of nodes: 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
Tree depth: The maximum level of all nodes in the tree

Tree representation

Ordinary notation

The implementation of this notation is complicated, and the implementation of array is adopted. When there are too many child nodes, the larger the dimension of array is, the lower the efficiency is.
Sibling notation

This representation can be implemented in a linked list, that is, to ensure that the locations between brothers are represented according to the left and right nodes, that is, the implementation of a binary tree, that is, all tree structures can be transformed into a binary tree form.
```
/ / A node
Node {
    this.data = data;
    this.leftChild = B;
    this.rightSibling = C
}
/ / C node
Node {
    this.data = data;
    this.leftChild = G;
    this.rightSibling = D
}
Copy the code
```

Binary tree

Binary tree: A tree with at most two subtrees per node is called a binary tree.

The characteristics of

A binary tree number twoiThe maximum node tree of layer is:2^(i - 1)
Depth ofkThe binary tree contains at most2^k-1A node
In the binary tree, there aren0One leaf node,n2A degree of2, thenn0 = n2 + 1

Special type

Full binary tree: A tree in which all nodes except leaf nodes contain two subtrees is called full binary tree

Complete binary tree: except for the last layer, the number of nodes in other layers reaches the maximum value, and the last layer has continuous leaf nodes from left to right, and only some nodes on the right are missing.

storage

Binary trees are commonly stored in arrays and linked lists

Use arrays: perfect binary trees or complete binary trees

Use linked lists: incomplete binary trees

Because if you continue to use arrays, you’re wasting space.

Binary search tree

The characteristics of

The key of the left node < the key of the parent node < the key of the right node

Code implementation

Initialize binary tree code

Three simple attributes are used here

Key: The size used to hold a value

Left: indicates the left subtree

Right: Used to indicate the number of words on the right

function BinarySearchTree() {
  // Node element
  function Node(key) {
    this.key = key // A key-value pair can be stored as a key-value pair
    this.left = null;
    this.right = null;
  }

  // Initialize the root node
  this.root = null;
}
Copy the code

The insert

Check whether there is a root node. If there is no root node, add it as root
Have root node –> add recursive insert method
Add to left node or right node –> If add to left node, check whether null, add to left node, and vice versa.

BinarySearchTree.prototype.insert = (key) = > {
    // 1. Create node elements
    const newNode = new Node(key);
    // 2. Check whether there is a root node
    if(this.root === null) {
      this.root = newNode
    }else {
      insertNode(this.root, newNode)
    }
  }

  // Insert recursive operations
  function insertNode(oldNode, newNode) {
    // 1. Check whether it is on the left node or the right node
    if( newNode.key < oldNode.key) {
      // 2. Check whether the left node is null
      if(oldNode.left === null) {
        // If it is null, it is added directly after
        oldNode.left = newNode;
      }else {
        // if not null, recurse again
        insertNode(oldNode.left, newNode)
      }
    }else {
      / / same as above
      if(oldNode.right === null) {
        oldNode.right = newNode;
      }else {
        insertNode(oldNode.right, newNode)
      }
    }
  }



// Test the insert code
const bsts = new BinarySearchTree();
bsts.insert(11)
bsts.insert(7)
bsts.insert(15)
bsts.insert(5)
bsts.insert(9)
bsts.insert(13)
bsts.insert(20)
bsts.insert(3)
bsts.insert(8)
bsts.insert(10)
bsts.insert(12)
bsts.insert(14)
bsts.insert(18)
bsts.insert(25)
bsts.insert(19)
Copy the code

After adding the test code, the view looks like this:

Traversal operation

The first sequence traversal

Processing the root node
The left node is traversed in order first
The right node is traversed in order

  BinarySearchTree.prototype.preOrder = function(cb) {
    _preOrderNode(this.root, cb)
  }
  // Iterate over the recursive function first
  function _preOrderNode(node, cb) {
    // Stop recursion if both the left and right subtrees are null during processing
    if(node ! = =null) {
      // 1 Handles the key and adds node.key via callback
      cb(node.key);
      // 2 processes the passed left subtree
      _preOrderNode(node.left, cb)
      // 3 Process the passed right subtree
      _preOrderNode(node.right, cb)

    }
  }
Copy the code

In the sequence traversal

The left node is traversed in middle order
Find the root node
In order to traverse the right node

BinarySearchTree.prototype.midOrder = function(cb) {
    _midOrderNode(this.root, cb)
  }
  function _midOrderNode(node, cb) {
    if(node ! = =null) {
      // 1. The left node is traversed in order
      _midOrderNode(node.left, cb)
      // 2. Find the root
      cb(node.key)
      // 3. Walk through the right node in order
      _midOrderNode(node.right, cb)
    }
  }
Copy the code

After the sequence traversal

The left subtree node is traversed sequentially
The right subtree node is traversed sequentially
Find the root node

BinarySearchTree.prototype.postOrder = function(cb) {
    _postOrderNode(this.root, cb)
  }
  function _postOrderNode(node, cb) {
    if(node ! = =null) {
      // 1. The left subtree node is traversed sequentially
      _postOrderNode(node.left, cb)
      // 2. The right subtree is traversed in sequence
      _postOrderNode(node.right, cb)
      // 3. Find the root
      cb(node.key)
    }
  }

Copy the code

The test code

// Run the test first
let pre = ""
bst.preOrder((key) = > {
  pre += key + ""
})
console.log("Sequential traversal test" + pre)

// Order traversal test
let mid = ""
bst.midOrder((key) = > {
  mid += key + ""
})
console.log("Middle order traversal test" +　mid)


// After the sequence traversal test
let post = ""
bst.postOrder((key) = > {
  post += key + ""
})
console.log("Post-order traversal test"+ POST) sequential traversal test11 7 5 3 9 8 10 15 13 12 14 20 18 19 25Medium order traversal test3 5 7 8 9 10 11 12 13 14 15 18 19 20 25Post-order traversal test3 5 8 10 9 7 12 14 13 19 18 25 20 15 11
Copy the code

To find the most value

Combined with the characteristics of binary search tree, the left subtree node < parent node < right subtree node

/** * Max Max * When the right subtree is null, the element is the maximum */
  BinarySearchTree.prototype.max = () = > {
    let node = this.root
    let key = null
    while(node) {
      key = node.key
      node = node.right
    }
    return key
  }

  /** * min * When the left subtree is null, the element is the smallest */
  BinarySearchTree.prototype.min = () = > {
    let node = this.root
    let key = null
    while(node) {
      key = node.key
      node = node.left
    }
    return key
  }
Copy the code

Searches for the presence of a key value

 /** * Searches for the presence of a key */
  BinarySearchTree.prototype.search = (key) = > {
    let current = this.root;
    while(current) {
      if(key < current.key) {
        current = current.left
      }else if (key > current.key){
        current = current.right;
      }else {
        return true}}return false;
  }
Copy the code

Delete operation

If the key is a leaf node, the parent node of the key points to NULL
If there is only one node after the key, the parent node of the key points to the child node of the key
If there are two nodes after the key, consider the precursor or successor nodes to fill in the key, and then adjust the subsequent node changes

/** * Delete a key * 1 if the key is a leaf node, the parent of the key points to null * 2 If there is only one node behind the key, the parent of the key points to the child of the key * 3. If there are two nodes after the key, you need to consider the precursor or successor nodes to fill, and then adjust the subsequent node changes */
  BinarySearchTree.prototype.remove = (key) = > {
    let current = this.root;
    Parent, isLeftChild, isLeftChild, isLeftChild, isLeftChild
    let parent = this.root;
    let isLeftChild = true
    // Find the current key location
    while(current.key ! == key) { parent = currentif(key < current.key) {
        current = current.left
        isLeftChild = true
      }else {
        current = current.right
        isLeftChild = false
      }
      // If current is null, exit directly
      if (current === null) {
        return false; }}const type = isLeftChild ? 'left' : 'right';
    // When there are only leaf nodes
    if(current.left === null && current.right === null) {
      if(current.key === this.root.key) {
        this.root = null
      }else {
        parent[type] = null}}// If there is only one left subtree node, we need to point parent to the child node
    else if (current.left === null && current.right) {
      // Point the parent node to the child node
      parent[type] = current.right
    } else if (current.right === null && current.left) {
      parent[type] = current.left
    }
    // There are two child nodes, which can find the precursor or successor
    // The tree is a little larger than the deleted node, i.e. the leftmost node in the right subtree
    else {
      // Find the successor node
      const node = _closeBigger(current.right)
      if(current.key === this.root.key) {
        this.root = node
        node.left = current.left
      }else {
        if(isLeftChild) {
          parent.left = node
          node.left = current.left
        }else {
          parent.right = node
          node.left = current.left
        }
      }
    }
  }
  // Find the successor node
  function _closeBigger(node) {
    let temp = node
    let current = null
    // Save the parent of a descendant node, because there may be descendants that are not nodes but nodes in the left subtree behind
    let currentParent = null
    while(node) {
      currentParent = current // Save the parent node
      current = node
      node = node.left
    }
    / / when the node key! If == current. Key, you need to adjust the node
    if(temp ! == current) {// By the nature of balanced binary trees, the leftmost is the smallest, when currentParent.left -> current. Right (present or null)
      currentParent.left = current.right
      current.right = currentParent
    }
    return current
  }
}
Copy the code

JS hash table implementation

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

JS tree structure

A Tree (Tree)

The definition of the tree

Tree representation

Binary tree

The characteristics of

Special type

storage

Binary search tree

The characteristics of

Code implementation

JS tree structure

A Tree (Tree)

The definition of the tree

Tree representation

Binary tree

The characteristics of

Special type

storage

Binary search tree

The characteristics of

Code implementation

Related Posts

Route usage changes caused by updates to the React-Router6 version

Write your own Babel

Autobinding, React, and ES6 classes