Introduction to code for implementing binary tree in javascript
This article brings you an introduction to the code for implementing binary trees in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.
Tree is the basic knowledge point of data structure. There is a special binary tree in the tree. I will not explain the concept of tree in detail here. I just use js to implement a simple binary tree
1 .Add node
2.Remove node
3.Maximum/minimum value of node
4.In-order traversal
5.Pre-order traversal
6.Post-order traversal
7 .Find whether the specified node exists
8. Whether it is an empty tree
Without further ado, let’s talk about the code. The first is the basic unit node class of the tree
/**
*left:左子树
*right:右子树
*value:节点值
*/
export default class BinaryNode {
constructor(val) {
this.value = val;
this.left = null;
this.right = null;
}
}The next is the binary tree class code
import BinaryNode from './BinaryNode'
export default class BinarySearchTree {
constructor() {
this.root = null;
this.values = new Array();
}
/**
* [insert 插入节点]
* @param {[type]} val [description]
* @return {[type]} [description]
*/
insert(val) {
this.values.push(val);
let node = new BinaryNode(val);
if (!this.root) {
this.root = node;
}else {
this._insertNode(this.root, node);
}
}
/**
* [remove 移除指定值]
* @param {[*]} val [目标值]
* @return {[type]} [description]
*/
remove(val) {
this.root = this._removeNode(this.root, val);
}
/**
* [search 检索]
* @param {[*]} val [被检索值]
* @return {[Boolean]} [表示是否存在]
*/
search(val) {
let values = this.inOrderTraverse();
return values.includes(val);
}
/**
* [min 返回最小值]
* @return {[type]} [description]
*/
min() {
let values = this.inOrderTraverse();
return values[0];
}
/**
* [max 返回最大值]
* @return {[type]} [description]
*/
max() {
let values = this.inOrderTraverse();
return values[values.length - 1];
}
/**
* [isEmpty 是否为空二叉树]
* @return {Boolean}
*/
isEmpty() {
return this.root === null;
}
/**
* [inOrderTraverse 中序遍历]
* @return {[Array]} [description]
*/
inOrderTraverse() {
let result = new Array();
this._inOrderTraverseNode(this.root, function(node) {
result.push(node.value);
})
return result;
}
/**
* [preOrderTraverse 先序遍历]
* @return {[Array]} [description]
*/
preOrderTraverse() {
let result = new Array();
this._preOrderTraverseNode(this.root, function(node) {
result.push(node.value);
})
return result;
}
/**
* [postOrderTraverse 后序遍历]
* @return {[Array]} [description]
*/
postOrderTraverse() {
let result = new Array();
this._postOrderTraverseNode(this.root, function(node) {
result.push(node.value);
})
return result;
}
/**
* [_insertNode 在指定节点插入节点]
* @param {[BinaryNode]} node [目标节点]
* @param {[BinaryNode]} newNode [待插入节点]
*/
_insertNode(node, newNode) {
if (node.value > newNode.value) {
if (node.left) {
this._insertNode(node.left, newNode);
}else {
node.left = newNode;
}
}else {
if (node.right) {
this._insertNode(node.right, newNode);
}else {
node.right = newNode;
}
}
}
/**
* [_removeNode 移除节点递归]
* @param {[BinaryNode]} node [当前节点]
* @param {[*]} val [要移的除节点值]
* @return {[BinaryNode]} [当前节点]
*/
_removeNode(node, val) {
if (node === null) {
return node;
}
//递归寻找目标节点
if (val < node.value) {
this._removeNode(node.left, val);
return node;
}
if (val > node.value) {
this._removeNode(node.right, val);
return node;
}
//找到目标节点
if (val === node.value) {
//为叶子节点
if (node.left === null && node.right === null) {
node = null;
return node;
}
//只有一个子节点
if (node.left === null) {
node = node.right;
return node;
}else if (node.right === null) {
node = node.left;
return node;
}
//有两个子节点
let min_node = this._findMinNode(node);
node.value = min_node.value;
node.right = this._removeNode(node.right, min_node.value);
return node;
}
}
/**
* [_findMinNode 查找最小节点]
* @param {[BinaryNode]} node [当前节点]
* @return {[BinaryNode]} [最小的节点]
*/
_findMinNode(node) {
while(node && node.left) {
node = node.left;
}
return node;
}
/**
* [_inOrderTraverseNode 中序遍历递归]
* @param {[BinaryNode]} node [当前节点]
* @param {Function} callback [回调函数]
* @return {[type]} [description]
*/
_inOrderTraverseNode(node, callback) {
if (node) {
this._inOrderTraverseNode(node.left, callback);
callback(node);
this._inOrderTraverseNode(node.right, callback);
}
}
/**
* [_preOrderTraverseNode 先序遍历递归]
* @param {[BinaryNode]} node [当前节点]
* @param {Function} callback [回调函数]
* @return {[type]} [description]
*/
_preOrderTraverseNode(node, callback) {
if (node) {
callback(node);
this._preOrderTraverseNode(node.left, callback);
this._preOrderTraverseNode(node.right, callback);
}
}
/**
* [_postOrderTraverseNode 后序遍历递归]
* @param {[BinaryNode]} node [当前节点]
* @param {Function} callback [回调函数]
* @return {[type]} [description]
*/
_postOrderTraverseNode(node, callback) {
if (node) {
this._postOrderTraverseNode(node.left, callback);
this._postOrderTraverseNode(node.right, callback);
callback(node);
}
}
}The functions of each function are in the comments. Recursion is used extensively to traverse the tree. The recursion here is relatively simple and easy to understand. Finding the maximum and minimum values here is lazy without recursive search, but in The maximum and minimum values are directly retrieved during sequential traversal. Note that these are values, not nodes of the tree. In fact, the code for finding the minimum node is also written as a private function, but it is not used for searching for the maximum and minimum values.
Of course, this is just a simple binary tree, and it can also be upgraded to an AVL tree, etc. I won’t go into details here
Related recommendations:
Detailed explanation of the use of JS binary search tree
Detailed explanation of binary tree traversal in JS_javascript skills
Implementation methods of pre-order, in-order and post-order traversal of binary trees in JS
The above is the detailed content of Introduction to code for implementing binary tree in javascript. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
Compare complex data structures using Java function comparison
Apr 19, 2024 pm 10:24 PM
When using complex data structures in Java, Comparator is used to provide a flexible comparison mechanism. Specific steps include: defining the comparator class, rewriting the compare method to define the comparison logic. Create a comparator instance. Use the Collections.sort method, passing in the collection and comparator instances.
Java data structures and algorithms: in-depth explanation
May 08, 2024 pm 10:12 PM
Data structures and algorithms are the basis of Java development. This article deeply explores the key data structures (such as arrays, linked lists, trees, etc.) and algorithms (such as sorting, search, graph algorithms, etc.) in Java. These structures are illustrated through practical examples, including using arrays to store scores, linked lists to manage shopping lists, stacks to implement recursion, queues to synchronize threads, and trees and hash tables for fast search and authentication. Understanding these concepts allows you to write efficient and maintainable Java code.
In-depth understanding of reference types in Go language
Feb 21, 2024 pm 11:36 PM
Reference types are a special data type in the Go language. Their values do not directly store the data itself, but the address of the stored data. In the Go language, reference types include slices, maps, channels, and pointers. A deep understanding of reference types is crucial to understanding the memory management and data transfer methods of the Go language. This article will combine specific code examples to introduce the characteristics and usage of reference types in Go language. 1. Slices Slices are one of the most commonly used reference types in the Go language.
PHP data structure: The balance of AVL trees, maintaining an efficient and orderly data structure
Jun 03, 2024 am 09:58 AM
AVL tree is a balanced binary search tree that ensures fast and efficient data operations. To achieve balance, it performs left- and right-turn operations, adjusting subtrees that violate balance. AVL trees utilize height balancing to ensure that the height of the tree is always small relative to the number of nodes, thereby achieving logarithmic time complexity (O(logn)) search operations and maintaining the efficiency of the data structure even on large data sets.
Full analysis of Java collection framework: dissecting data structure and revealing the secret of efficient storage
Feb 23, 2024 am 10:49 AM
Overview of Java Collection Framework The Java collection framework is an important part of the Java programming language. It provides a series of container class libraries that can store and manage data. These container class libraries have different data structures to meet the data storage and processing needs in different scenarios. The advantage of the collection framework is that it provides a unified interface, allowing developers to operate different container class libraries in the same way, thereby reducing the difficulty of development. Data structures of the Java collection framework The Java collection framework contains a variety of data structures, each of which has its own unique characteristics and applicable scenarios. The following are several common Java collection framework data structures: 1. List: List is an ordered collection that allows elements to be repeated. Li
Hash table-based data structure optimizes PHP array intersection and union calculations
May 02, 2024 pm 12:06 PM
The hash table can be used to optimize PHP array intersection and union calculations, reducing the time complexity from O(n*m) to O(n+m). The specific steps are as follows: Use a hash table to map the elements of the first array to a Boolean value to quickly find whether the element in the second array exists and improve the efficiency of intersection calculation. Use a hash table to mark the elements of the first array as existing, and then add the elements of the second array one by one, ignoring existing elements to improve the efficiency of union calculations.
PHP SPL data structures: Inject speed and flexibility into your projects
Feb 19, 2024 pm 11:00 PM
Overview of the PHPSPL Data Structure Library The PHPSPL (Standard PHP Library) data structure library contains a set of classes and interfaces for storing and manipulating various data structures. These data structures include arrays, linked lists, stacks, queues, and sets, each of which provides a specific set of methods and properties for manipulating data. Arrays In PHP, an array is an ordered collection that stores a sequence of elements. The SPL array class provides enhanced functions for native PHP arrays, including sorting, filtering, and mapping. Here is an example of using the SPL array class: useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array
Learn the secrets of Go language data structures in depth
Mar 29, 2024 pm 12:42 PM
In-depth study of the mysteries of Go language data structure requires specific code examples. As a concise and efficient programming language, Go language also shows its unique charm in processing data structures. Data structure is a basic concept in computer science, which aims to organize and manage data so that it can be accessed and manipulated more efficiently. By in-depth learning the mysteries of Go language data structure, we can better understand how data is stored and operated, thereby improving programming efficiency and code quality. 1. Array Array is one of the simplest data structures
