Binary tree is one of the common data structures, of course, it is also one of the data structures that programmers must be familiar with. In my freshman year, I used C++ and C language to implement it, and then I used javascript recently. I just write the javascript version of binary tree, I believe it is not too difficult.

Create a binary tree

Some common binary trees

If you’ve studied binary trees, you know that a binary tree can only have two branches, or no branches at all. Here is a common binary tree:

Degenerate into a linear list

The implementation code

Binary trees are usually created in the form of classes, although JavScript now has classes, but for the sake of familiarity with stereotypes, we’ll use stereotypes to simulate the behavior of classes. Here is the implementation code:

function Node(){
    this.data = null
    this.leftChild = null
    this.rightChild = null
}

function BinaryTree(){
    Node.call(this)
    this.root = null
}
Copy the code

You can see that there are two classes defined here, a Node class and a binaryTree class. One node contains the data field, its left pointer and its right pointer, and a tree contains all the properties that the node contains, as well as a root node. Here can be seen as the tree is a subclass of nodes, the following uses the prototype to realize the inheritance relationship between them:

// Implement inheritance; (function () {
    const F = function () {}
    F.prototype = Node.prototype
    BinaryTree.prototype = new F()
    BinaryTree.prototype.constructor = BinaryTree
})()

BinaryTree.prototype.insertNode = function(data){
    if(this.root === null) {this.root = {}
    	this.root.data = data
    }else{
    	insertNode(this.root, data)
    }
}
Copy the code

Walk through the binary tree

Common binary tree traversal methods include: pre-order traversal, post-order traversal, middle-order traversal and hierarchical traversal. These traversal methods can be achieved by recursion. Of course, it is also possible to achieve it by queue or stack, but recursion is to be more concise, the code is as follows:

BinaryTree.prototype.travelTree = function (root) { // preorder traversal
    console.log(root.data)
    this.travelTree(root.leftChild)
    this.travelTree(root.rightChild)
}
Copy the code

Above is javascript implementation of binary tree creation and traversal, complete code please click

Scan the QR code below or search for “Teacher Tony’s front-end cram school” to follow my wechat official account, and then you can receive my latest articles in the first time.