An overview of the

A node in a binary tree can have at most two child nodes: one on the left and one on the right. There are two types of nodes in a binary tree: one is called “inner node” with child nodes; One that has no children is called a leaf node.

A standard binary tree would look like this.

Create BST (binary lookup tree)

Binary search tree is a special binary tree, the node on the left of the tree must be smaller than the node on the right.

Demand analysis

Node class: each node must have a key and left and right Pointers. Binary tree class: need a root node (root), need a node method (insert).

Code implementation


/ / the node class
class Node {
  constructor(key) {
  	// The element to be created
    this.key = key
    / / pointer to the left
    this.left = null
    / / right pointer
    this.right = null}}// Binary tree class
class BinarySearchTree {
  constructor() {
  	/ / with a node
    this.root = null
  }
  // Insert node method
  insert(key){}}Copy the code

Requirement analysis for inserting nodes

If you look carefully, you will find that the insert method above is not implemented. It is not difficult to implement, but MY intention is to let you know why it is done, rather than directly paste the code.

Do not know whether the mobile phone can see clearly, the picture of the text, here or the text inside the post.

① The first time it came in, it was still an empty tree, that is, there was no root node; Suppose you want to insert a node 11, but there is no root node yet, so that 11 should be the root node
② If a node 7 is inserted next time, the tree should have a root node. The node inserted this time should become a child node instead of a root node. Whose child node should it be? Should it be the left node or the right node?
2.1: The home page should be compared from the root node, the root node is 11, and the node to be inserted is 7,7 is smaller than 11, so 7 should be on the left of the parent node, but on the right.
2.2 (this is the red part of the figure) In the first case, it is assumed that the current root node has no left node, and node 7 to be inserted becomes the left node of 11 naturally.
2.3: (green) on the drawing the second case, assuming that the root node has now left eight nodes, so now to insert nodes 7 nodes can no longer be 11 left, it will only continue to go down, continue to contrast with 8, 2.1 steps again now, just changed the root node for the 8, therefore, add a node is a recursive process.

The code implements the insert node requirement


class BinarySearchTree {
  constructor() {
    this.root = null
    this.tree = []
  }

  insert(key) {
  	// Add the root node if it does not already exist
    if (this.root === null) {
      this.root = new Node(key)
    } else {
      // Add the left or right node if there is a root node
      this.insertNode(this.root, key)
    }
  }

  insertNode(node, key) {
  	// If the node to be added is smaller than the parent node, go through the process of adding a left node, and go through the process of adding a right node
    if (node.key > key) {
      // If the current node doesn't already have a left node, add it. Otherwise, insertNode continues recursively until it finds the right place to create it
      node.left === null ? node.left = new Node(key) : this.insertNode(node.left, key)
    } else {
     // If the current node doesn't have a right node, add it. Otherwise, insertNode continues recursively until it finds the right place to create it
      node.right === null ? node.right = new Node(key) : this.insertNode(node.right, key)
    }
  }
}
Copy the code

Test insert node instance


let tree = new BinarySearchTree()

tree.insert(11)

tree.insert(7)

tree.insert(15)

tree.insert(5)

tree.insert(9)

tree.insert(13)

console.log(tree.root)

Copy the code

The code structure is shown above

Traversal of binary trees

Binary tree traversal

Middle: middle node (also known as parent node); Right: right node; Left: left node.

Middle-order traversal: traversal of all nodes in the sequence visited by the above lines, that is, all nodes are accessed in the order from smallest to largest; The access rules are left center right.
Sequential traversal: first accesses the root node, then accesses the left and right subtrees in the same manner; Access rules are left and right.
Back-order traversal: first visit the leaf node, from the left subtree to the right subtree, then to the root node; Access rules are left and right center.

In the sequence traversal

Following the rule of middle order traversal (left center right), how should the top tree traverse?

①: according to the rules for the first time, it can be divided into three parts [22,10,30],[56],[81,77,92] according to the rules.
②: the second split, the first part is the internal node, can also be split in accordance with the rules [10,22,30], the second part, is already a leaf node, do not need to be removed, drag down directly [56], the third part, or the internal node, can also be split in accordance with the rules [77,81,92], as shown in the figure above.
③ : After the second splitting, all nodes form leaf nodes, so there is no need to continue the splitting, so the final middle-order traversal result is: [10, 22, 30, 56, 77, 81, 92], as shown in the figure above.
④ It is clear that this process is a recursive one.

With the traversal rules sorted out, it’s easy to implement in code.

Code implementation


class BinarySearchTree {
	constructor(){...// Store the result of the traversal
      this.tree = []
    }
	...
    // middle order traversal
    inOrderTraverseNode(node) {
      if(node ! = =null) {
        this.inOrderTraverseNode(node.left)
        this.tree.push(node.key)
        this.inOrderTraverseNode(node.right)
      }
    }
}

let tree = new BinarySearchTree()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
// Start at the root
tree.inOrderTraverseNode(tree.root)
console.log(tree.tree) //[10, 22, 30, 56, 77, 81, 92]

Copy the code

The code implementation is very simple just a few lines.

The first sequence traversal

In accordance with the rules of sequence traversal (left and right), presumably if you understand the above sequence traversal, sequence traversal is like a fish in water, saliva is available, fast horse whip, nine cows and a tiger, Pythagorean theorem, lever principle… The matter.

①: for the first time, it can be divided into three parts [56],[22,10,30],[81,77,92] according to the rules.
②: the second split, the first part, is already a leaf node, do not need to be removed, drag down directly [56], the second part and is an internal node, can also be split in accordance with the rules [22,10,30], the third part, or internal nodes, can also be split in accordance with the rules [81,77,92], as shown in the figure above.
③ : After the second splitting, all nodes form leaf nodes, so there is no need to continue the splitting, so the final middle-order traversal result is: [56, 22, 10, 30, 81, 77, 92], as shown in the figure above.

Code implementation


class BinarySearchTree {...// order traversal first
   	preOrderTraverseNode(node) {
      if(node ! = =null) {
        this.tree.push(node.key)
        this.preOrderTraverseNode(node.left)
        this.preOrderTraverseNode(node.right)
     }
    }
}

let tree = new BinarySearchTree()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
// Start at the root
tree.postOrderTraverse(tree.root)
console.log(tree.tree) //[56, 22, 10, 30, 81, 77, 92]

Copy the code

Preorder traversal and preorder traversal code is much the same.

After the sequence traversal

If both types of traversal are understood, then the sequential traversal is… The matter.

①: for the first time, it can be divided into three parts [22,10,30],[81,77,92],[56] according to the rules, as shown in the figure above.
②: the second split, the first part, and the internal node, can also be split in accordance with the rules [10,30,22], the second part or the internal node, can also be split in accordance with the rules [77,92,81], the third part, is already leaf nodes, do not need to be removed, directly drag down [56], as shown in the figure above.
③ : After the second splitting, all nodes form leaf nodes, so there is no need to continue the splitting. Therefore, the final middle-order traversal result is as follows: [10, 30, 22, 77, 92, 81, 56], as shown in the figure above.

Binary tree search

Search maximum node
Search minimum node
Searches for the existence of a node

Search maximum node

That’s right. Again, take this picture. Surprise no.

According to the rules of binary trees, small values are on the left and large values are on the right. So the largest node must be the one at the bottom right of the leaf.

Code implementation


class BinarySearchTree {...maxNode(node) {
      // Keep looking to the right until you find the rightmost leaf
      while(node.right ! = =null) {
        node = node.right
      }
      return node
    }
}
...
let tree = new BinarySearchTree()

tree.maxNode(tree.tree) / / 92

Copy the code

The implementation code is also very simple.

Search minimum node

According to the rules of binary trees, small values are on the left and large values are on the right. So the smallest node must be the leaf node at the bottom left, just the opposite of the largest node.

Code implementation


class BinarySearchTree {...minNode(node) {
      // Keep looking to the left until you find the leftmost leaf
      while(node.left ! = =null) {
        node = node.left
      }
      return node
    }
}
...
let tree = new BinarySearchTree()

tree.minNode(tree.tree) / / 10

Copy the code

Search for a specific node

Search for a specific node, also starting from the root node, the current node is the same as the specified node, return true; It depends on whether the specified node is smaller or larger than the current node. If the specified node is smaller, go to the left. If the specified node is larger, go to the right until it is found or null.

Code implementation


class BinarySearchTree {...searchNode(node, key) {
      if (node === null) return false
      if (node.key === key) {
        return true
      } else {
        return node.key > key ? this.searchNode(node.left, key) : this.searchNode(node.right, key)
      }
    }
}
...
let tree = new BinarySearchTree()
// start with the root.
let res = tree.searchNode(tree.root, 199)
console.log(res) // false

Copy the code

Deletes a specific node

Why delete the node last? In fact, I didn’t plan to write this part at the beginning, because it was difficult to understand and I didn’t know if I could describe it clearly. However, after writing the article, I always felt that without this part, the article would be incomplete and missing something.

There are three scenarios for node deletion

The node to be deleted has no left or right nodes. This is easier to handle. Set the node to be deleted directly to NULL or return NULL directly.
② : There is one of the left and right nodes of the node to be deleted. In this case, the left or right node should be returned to the previous parent node.
③ : to delete the nodes have left and right nodes, this is the most complex situation, first find the node to delete, and then find the right of the node to delete the smallest node, or the largest node on the left, to replace the node to delete, finally, and then just find the largest node (minimum node) delete.

Code implementation



class BinarySearchTree {...removeNode(node,key){
    if (node === null) return null
    if (node.key === key) {
      / / a
      if(node.left === null && node.right === null) {return null
      / / 2
      }else if(node.left === null || node.right === null) {let key = node.left ? 'left' : 'right'
        return node[key]
      / / is three
      }else{
        let aux =this.minNode(node.right)
        node.key = aux.key
        node.right = this.removeNode(node.right, aux.key)
        return node
      }
    } else {
      let nodeKey = node.key > key ? "left" : "right"
      node[nodeKey] = node.key > key ? this.removeNode(node.left, key) : this.removeNode(node.right, key)
      return node
    }
  }
}

Copy the code

The complete code


class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null}}class BinarySearchTree {
  constructor() {
    this.root = null
    this.tree = []
  }

  insert(key) {
    if (this.root === null) {
      this.root = new Node(key)
    } else {
      this.insertNode(this.root, key)
    }
  }

  insertNode(node, key) {
    if (node.key > key) {
      node.left === null ? node.left = new Node(key) : this.insertNode(node.left, key)
    } else {
      node.right === null ? node.right = new Node(key) : this.insertNode(node.right, key)
    }
  }

  inOrderTraverseNode(node) {
    if(node ! = =null) {
      this.inOrderTraverseNode(node.left)
      this.tree.push(node.key)
      this.inOrderTraverseNode(node.right)
    }
  }

  preOrderTraverseNode(node) {
    if(node ! = =null) {
      this.tree.push(node.key)
      this.preOrderTraverseNode(node.left)
      this.preOrderTraverseNode(node.right)
    }
  }

  postOrderTraverse(node) {
    if(node ! = =null) {
      this.postOrderTraverse(node.left)
      this.postOrderTraverse(node.right)
      this.tree.push(node.key)
    }
  }

  minNode(node) {
    while(node.left ! = =null) {
      node = node.left
    }
    return node
  }

  maxNode(node) {
    while(node.right ! = =null) {
      node = node.right
    }
    return node
  }

  searchNode(node, key) {
    if (node === null) return false
    if (node.key === key) {
      return true
    } else {
      return node.key > key ? this.searchNode(node.left, key) : this.searchNode(node.right, key)
    }
  }
  
  removeNode(node,key){
    if (node === null) return null
    if (node.key === key) {
      if(node.left === null && node.right === null) {return null
      }else if(node.left === null || node.right === null) {let key = node.left ? 'left' : 'right'
        return node[key]
      }else{
        let aux =this.minNode(node.right)
        node.key = aux.key
        node.right = this.removeNode(node.right, aux.key)
        return node
      }
    } else {
      let nodeKey = node.key > key ? "left" : "right"
      node[nodeKey] = node.key > key ? this.removeNode(node.left, key) : this.removeNode(node.right, key)
      return node
    }
  }

}


Copy the code

Reorganization of binary trees

What does regrouping binary trees mean? So instead of giving you a binary tree and asking you to find its first, middle, and last traversal, you’re given a binary tree that’s first, middle, and last backward.

According to the preorder [1,2,4,7,3,5,6,8] and the middle order [4,7,2,1,5,3,8,6], restructure the binary tree.

Analysis of the topic:

We’re talking about regrouping binary trees, not BST, so there’s no notion of little on the left, big on the right.
If you reorganize a binary tree, you can go first, middle, and last
The first node in the sequence must be the root node (also known as the parent node).
② : Find the root position in the middle sequence table, and then according to this position, find the left node and the right node of the first and middle order
Recurse steps ①, ② until the node is null/undefinde.

Code implementation


class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null}}let preOrder = [1.2.4.7.3.5.6.8]

let inOrder = [4.7.2.1.5.3.8.6]

class regroupTree{
  constructor(){
    this.root = null
  }
  sliceTree(preOrder,inOrder){
    let node = preOrder[0]
    // Check whether the root node exists
    if(node){
      // Locate the root node in the sequence table
      let index = inOrder.indexOf(node)
      // Find the middle order of the left node through the root node position
      let inOrderLeft = inOrder.slice(0,index)
      // Find the middle order of the right node by the root node position
      let inOrderRight = inOrder.slice(index+1)
      // Find the order of the left node through the root node position
      let preOrderLeft = preOrder.slice(1,index+1)
      // Find the order of the right node by the root node position
      let preOrderRight = preOrder.slice(index+1)
      let root = new Node(node)
      root.left = this.sliceTree(preOrderLeft,inOrderLeft)
      root.right = this.sliceTree(preOrderRight,inOrderRight)
      return root
    }
  }
  buildTree(preOrder,inOrder){
    this.root = this.sliceTree(preOrder,inOrder)
  }
}

let tree = new regroupTree()
tree.buildTree(preOrder,inOrder)
console.log(tree.tree)

Copy the code

Add two methods (first order traversal, middle order traversal) to verify


let preOrder = [1.2.4.7.3.5.6.8]

let inOrder = [4.7.2.1.5.3.8.6]

class regroupTree{
  constructor(){...this.tree = []
  }
  ...
  inOrderTraverseNode(node) {
    if (node) {
      this.inOrderTraverseNode(node.left)
      this.tree.push(node.key)
      this.inOrderTraverseNode(node.right)
    }
  }

  preOrderTraverseNode(node) {
    if (node) {
      this.tree.push(node.key)
      this.preOrderTraverseNode(node.left)
      this.preOrderTraverseNode(node.right)
    }
  }
}

let tree = new regroupTree()
tree.buildTree(preOrder,inOrder)
tree.preOrderTraverseNode(tree.root) / /,2,4,7,3,5,6,8 [1]
/ / tree. PreOrderTraverseNode (tree. The root),7,2,1,5,3,8,6 [4]

Copy the code

At the end

After reading, I hope you have a deeper understanding of binary tree concepts, traversal rules, find the largest node, the smallest node, find characteristic nodes, delete specific nodes, and binary tree reorganization. I hope you have no white points come in 🤡 this time

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.

Everyone can understand | binary tree data structure

An overview of the

Create BST (binary lookup tree)

Demand analysis

Code implementation

Requirement analysis for inserting nodes

The code implements the insert node requirement

Test insert node instance

Traversal of binary trees

Binary tree traversal

In the sequence traversal

Code implementation

The first sequence traversal

Code implementation

After the sequence traversal

Binary tree search

Search maximum node

Code implementation

Search minimum node

Code implementation

Search for a specific node

Code implementation

Deletes a specific node

Code implementation

The complete code

Reorganization of binary trees

According to the preorder [1,2,4,7,3,5,6,8] and the middle order [4,7,2,1,5,3,8,6], restructure the binary tree.

Code implementation

Add two methods (first order traversal, middle order traversal) to verify

At the end

Everyone can understand | binary tree data structure

An overview of the

Create BST (binary lookup tree)

Demand analysis

Code implementation

Requirement analysis for inserting nodes

The code implements the insert node requirement

Test insert node instance

Traversal of binary trees

Binary tree traversal

In the sequence traversal

Code implementation

The first sequence traversal

Code implementation

After the sequence traversal

Binary tree search

Search maximum node

Code implementation

Search minimum node

Code implementation

Search for a specific node

Code implementation

Deletes a specific node

Code implementation

The complete code

Reorganization of binary trees

According to the preorder [1,2,4,7,3,5,6,8] and the middle order [4,7,2,1,5,3,8,6], restructure the binary tree.

Code implementation

Add two methods (first order traversal, middle order traversal) to verify

At the end

Related Posts

24 Suggestions for Front-end Performance Optimization (2020)

ES6 Learn to deconstruct assignment

Vue3 source code series dependency collection implementation