preface

Every time after a long holiday, I will habitually reflect and review their own technology, especially the Dragon Boat Festival. Why did I write about binomial trees? In fact, this involves a programmer growth problem. For 0-3 years of front-end programmers, there may be little opportunity to work on data structures and algorithms, except in large factories or architecture related work. However, many front-end engineers who have worked for 2-3 years are already relatively familiar with business work and have used various technologies more or less. At this stage, should every programmer with ambition break through their own technical bottlenecks and study some deeper knowledge? Yes, at this stage, we should most understand the knowledge related to data structure, algorithm and design pattern. The author has systematically summarized the design pattern and algorithm in the previous article. If you are interested, you can learn about it.

Next, the author summarizes the knowledge of binary tree, and through the actual code step by step to take you to achieve a binary search tree.

Introduction to binary trees

Binary tree is an important type of tree structure. The data structure abstracted from many practical problems is often in the form of binary tree, even the general tree can be simply converted to binary tree, and the storage structure and algorithm of binary tree are relatively simple, so the binary tree is particularly important. The characteristic of binary tree is that each node can have at most two subtrees, and can be divided into left and right.

Left child node
Right child node
Binary search tree (BST)

Implement a binary search (BST) tree

Before implementing it, we need to analyze the BST (binary search) tree. To build a practical tree, we need nodes and methods, as shown below:

function BinarySearchTree() {
    let Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    let root = null;
}
Copy the code

We according to the above binary search tree structure organization, to achieve the basic method of binary tree.

/ / insert
this.insert = function(key) {
    let newNode = new Node(key);
    if(root === null) {
        root = newNode;
    }else{ insertNode(root, newNode); }}Copy the code

Where insertNode method is used to judge the execution logic when the root node is not empty, the specific code is as follows:

function insertNode(node, newNode) {
    // If the new node value is less than the current node value, the left child node is inserted
    if(newNode.key < node.key) {
        if(node.left === null) {
            node.left = newNode;
        }else{ insertNode(node.left, newNode); }}else {
    // If the value of the new node is greater than the value of the current node, the right child node is inserted
        if(node.right === null) {
            node.right = newNode;
        }else{ insertNode(node.right, newNode); }}}Copy the code

The above code implements part of the BST insertion logic, and the specific usage is as follows:

let tree = new BinarySearchTree()
tree.insert(19)
tree.insert(10)
tree.insert(20)
Copy the code

The binary tree structure generated by the above code is as follows:

Tree traversal

Tree traversal is the process of visiting each node of the tree and performing some kind of operation on them. Specifically divided into sequence traversal, sequence traversal and sequence traversal. I will introduce them to you one by one.

In the sequence traversal

Middle-order traversal is a traversal mode that accesses all nodes in the order from smallest to largest, which is implemented as follows:

this.inOrderTraverse = function(cb) {
    inOrderTraverseNode(root, cb)
}

function inOrderTraverseNode(node, cb) {
    if(node ! = =null) {
        inOrderTraverseNode(node.left, cb)
        cb(node.key)
        inOrderTraverseNode(node.right, cb)
    }
}
Copy the code

The specific traversal process is shown in the figure below:

The first sequence traversal

A sequential traversal accesses each node in order of precedence over subsequent nodes. The concrete implementation is as follows:

this.preOrderTraverse = function(cb) {
    preOrderTraverseNode(root, cb)
}

function preOrderTraverseNode(node, cb) {
    if(node ! = =null) {
        cb(node.key)
        preOrderTraverseNode(node.left, cb)
        preOrderTraverseNode(node.right, cb)
    }
}
Copy the code

The specific traversal is shown in the figure below:

After the sequence traversal

Backorder traversal is to visit the descendants of the node first, and then the node itself. The concrete implementation is as follows:

this.postOrderTraverse = function(cb) {
    preOrderTraverseNode(root, cb)
}

function postOrderTraverseNode(node, cb) {
    if(node ! = =null) {
        postOrderTraverseNode(node.left, cb)
        postOrderTraverseNode(node.right, cb)
        cb(node.key)
    }
}
Copy the code

The specific traversal sequence is shown in the figure below:

The search tree

Our normal search will have a maximum search (that is, a maximum, a minimum, a median) and a search for a specific value, and we’ll implement them.

Search for a specific value

Search the BST tree for a specific value as follows:

this.search = function(key) {
    return searchNode(root, key)
}

function searchNode(ndoe, key) {
    if(node === null) {
        return false
    }
    if(key < node.key) {
        return searchNode(node.left, key)
    }else if(key > node.key) {
        return searchNode(node.right, key)
    }else {
        return true}}Copy the code

The implementation logic is also very simple, and you can explore it here.

Search minimum

According to the structural characteristics of binary tree, we can find that the most left end of binary tree is the minimum value, and the most right end of binary tree is the maximum value, so we can find the minimum value through traversing, the code is as follows:

this.min = function() {
    return minNode(root)
}

function minNode(node) {
    if(node) {
        while(node && node.left ! = =null) {
            node = node.left;
        }
        return node.key
    }
    return null
}
Copy the code

Search maximum

As with minima, maxima can be used in a similar way, as follows:

this.max = function() {
    return maxNode(root)
}

function maxNode(node) {
    if(node) {
        while(node && node.right ! = =null) {
            node = node.right;
        }
        return node.key
    }
    return null
}
Copy the code

Remove node

Removing nodes in BST is relatively complex and requires many considerations, as follows:

  1. Remove a leaf node
  2. Removes a node that has a left or right child node
  3. Remove a node that has two child nodes

With that in mind, we start to implement the logic for deleting nodes:

this.remove = function(key) {
    root = removeNode(root, key)
}

function removeNode(node, key) {
    if(node === null) {
        return null
    }
    if(key < node.key) {
        node.left = removeNode(node.left, key)
        return node
    }else if(key > node.key) {
        node.right = removeNode(node.right, key)
        return node
    }else {
        // a leaf node
        if(node.left === null && node.right === null) {
            node = null;
            return node
        }
        // A node with only one child node
        if(node.left === null) {
            node = node.right;
            return node
        }else if(node.right === null) {
            node = node.left;
            return node
        }
        // A node with two children
        let aux = findMinNode(node.right);
        node.key = aux.key;
        node.right = removeNode(node.right, aux.key);
        return node
    }
}

function findMinNode(node) {
    if(node) {
        while(node && node.left ! = =null) {
            node = node.left;
        }
        return node
    }
    return null
}
Copy the code

At this point, a complete search binary tree is realized, isn’t it a sense of accomplishment? The source of this article was uploaded to the author’s Github, interested friends can feel it.

Application of binary tree

Binary trees can be used to:

  • Spanning tree structure
  • Database search algorithm
  • Use binary tree encryption
  • Calculate the size of all files in directories and subdirectories,
  • Print a structured document
  • In the game used to do path planning, etc

extension

But trees type and a lot of kinds, these different types of trees in a computer have a wide range of USES, such as red and black tree, B tree, self-balancing binary search trees, space partitioning tree, hash tree, Hilbert R tree, etc., these trees dare if interested in friends can be in-depth study, technical field of vision for yourself in the future, after all, is very helpful.

The last

If you want to learn more front-end skills, actual combat and learning routes, welcome to join our technology group in the public account “Interesting Talk front-end” to study and discuss together, explore the frontier of the front-end.

reference

Binary tree – baike.baidu.com/item/ binary tree

More recommended

  • When the back end throws you 100,000 pieces of data at once, what do you do as a front end engineer?
  • Summary of several common sorting algorithms and search algorithms necessary for programmers
  • Implementing a CMS full stack project from 0 to 1 based on nodeJS (part 1)
  • Implementing a CMS full stack project from 0 to 1 based on nodeJS
  • Vue and React
  • From zero to one teaches you to develop a component library based on VUE
  • Build front-end team component systems from 0 to 1