Web Front-end
JS Tutorial
Use JS to implement the establishment of a binary search tree and some traversal methods
Use JS to implement the establishment of a binary search tree and some traversal methods
This article mainly introduces the establishment of a binary search tree implemented in JS and the implementation of some traversal methods. It has certain reference value and interested friends can refer to it.
Binary search tree is composed of nodes and edges.
We can define a node class Node, which stores the node data and the left and right sub-nodes, and then define a method for displaying the data:
//以下定义一个节点类
function Node(data,left,right){
// 节点的键值
this.data = data;
// 左节点
this.left = left;
// 右节点
this.right = left;
// 显示该节点的键值
this.show = show;
}
// 实现show方法
function show(){
return this.data;
}Then define a binary search tree class BST. This class defines the root node of the tree, initializes it to null, and then defines the method of inserting the node, and the method of traversing one side:
// 二叉查找树BST
// 有一个节点属性，还有一些其他的方法，以下定义一个二叉查找树BST类
function BST(){
// 根节点初始化为空
this.root = null;
// 方法
// 插入
this.insert = insert;
// Use JS to implement the establishment of a binary search tree and some traversal methods
this.inorder = inorder;
// Use JS to implement the establishment of a binary search tree and some traversal methods
this.preorder = preorder;
// Use JS to implement the establishment of a binary search tree and some traversal methods
this.postorder = postorder;
}
//实现insert插入方法
function insert(data){
// 创建一个节点保存数据
var node = new Node(data,null,null);
// 下面将节点node插入到树中
// 如果树是空的，就将节点设为根节点
if(!this.root){
this.root = node;
}else{ //树不为空
// 判断插在父节点的左边还是右边
// 所以先要保存一下父节点
// var parent = this.root;
var current = this.root;
var parent;
// 如果要插入的节点键值小于父节点键值，则插在父节点左边，
// 前提是父节点的左边为空，否则要将父节点往下移一层，
// 然后再做判断
while(true){
// data小于父节点的键值
parent = current;
if(data < parent.data){
// 将父节点往左下移(插入左边)
// parent = parent.left;
current = current.left;
// 如果节点为空，则直接插入
if(!current){
// ！！！此处特别注意，如果就这样把parent赋值为node，也仅仅只是parent指向node，
// 而并没有加到父元素的左边！！！根本没有加到树中去。所以要先记住父元素，再把当前元素加入进去
parent.left = node;
break;
}
}else{ // 将父节点往右下移(插入右边)
current = current.right;
if(!current){
parent.right = node;
break;
}
}
}
}
}
//实现inorder遍历方法(左中右)
function inorder(node){
if(node){
inorder(node.left);
console.log(node.show());
inorder(node.right);
}
}
// Use JS to implement the establishment of a binary search tree and some traversal methods(中左右)
function preorder(node){
if(node){
console.log(node.show());
preorder(node.left);
preorder(node.right);
}
}
// Use JS to implement the establishment of a binary search tree and some traversal methods(左右中)
function postorder(node){
if(node){
preorder(node.left);
preorder(node.right);
console.log(node.show());
}
}Test:
// Use JS to implement the establishment of a binary search tree and some traversal methods(左右中)
function postorder(node){
if(node){
postorder(node.left);
postorder(node.right);
console.log(node.show());
}
}
// 实例化一个BST树
var tree = new BST();
// 添加节点
tree.insert(30);
tree.insert(14);
tree.insert(35);
tree.insert(12);
tree.insert(17);
// Use JS to implement the establishment of a binary search tree and some traversal methods
tree.inorder(tree.root);
// Use JS to implement the establishment of a binary search tree and some traversal methods
tree.preorder(tree.root);
// Use JS to implement the establishment of a binary search tree and some traversal methods
tree.postorder(tree.root);Result:
In-order traversal:
Pre-order traversal:
Post-order traversal:
The above is the detailed content of Use JS to implement the establishment of a binary search tree and some traversal methods. 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
How to use JS and Baidu Maps to implement map pan function
Nov 21, 2023 am 10:00 AM
How to use JS and Baidu Map to implement map pan function Baidu Map is a widely used map service platform, which is often used in web development to display geographical information, positioning and other functions. This article will introduce how to use JS and Baidu Map API to implement the map pan function, and provide specific code examples. 1. Preparation Before using Baidu Map API, you first need to apply for a developer account on Baidu Map Open Platform (http://lbsyun.baidu.com/) and create an application. Creation completed
Recommended: Excellent JS open source face detection and recognition project
Apr 03, 2024 am 11:55 AM
Face detection and recognition technology is already a relatively mature and widely used technology. Currently, the most widely used Internet application language is JS. Implementing face detection and recognition on the Web front-end has advantages and disadvantages compared to back-end face recognition. Advantages include reducing network interaction and real-time recognition, which greatly shortens user waiting time and improves user experience; disadvantages include: being limited by model size, the accuracy is also limited. How to use js to implement face detection on the web? In order to implement face recognition on the Web, you need to be familiar with related programming languages and technologies, such as JavaScript, HTML, CSS, WebRTC, etc. At the same time, you also need to master relevant computer vision and artificial intelligence technologies. It is worth noting that due to the design of the Web side
How to create a stock candlestick chart using PHP and JS
Dec 17, 2023 am 08:08 AM
How to use PHP and JS to create a stock candle chart. A stock candle chart is a common technical analysis graphic in the stock market. It helps investors understand stocks more intuitively by drawing data such as the opening price, closing price, highest price and lowest price of the stock. price fluctuations. This article will teach you how to create stock candle charts using PHP and JS, with specific code examples. 1. Preparation Before starting, we need to prepare the following environment: 1. A server running PHP 2. A browser that supports HTML5 and Canvas 3
Essential tools for stock analysis: Learn the steps to draw candle charts with PHP and JS
Dec 17, 2023 pm 06:55 PM
Essential tools for stock analysis: Learn the steps to draw candle charts in PHP and JS. Specific code examples are required. With the rapid development of the Internet and technology, stock trading has become one of the important ways for many investors. Stock analysis is an important part of investor decision-making, and candle charts are widely used in technical analysis. Learning how to draw candle charts using PHP and JS will provide investors with more intuitive information to help them make better decisions. A candlestick chart is a technical chart that displays stock prices in the form of candlesticks. It shows the stock price
How to use JS and Baidu Map to implement map click event processing function
Nov 21, 2023 am 11:11 AM
Overview of how to use JS and Baidu Maps to implement map click event processing: In web development, it is often necessary to use map functions to display geographical location and geographical information. Click event processing on the map is a commonly used and important part of the map function. This article will introduce how to use JS and Baidu Map API to implement the click event processing function of the map, and give specific code examples. Steps: Import the API file of Baidu Map. First, import the file of Baidu Map API in the HTML file. This can be achieved through the following code:
How to use JS and Baidu Maps to implement map heat map function
Nov 21, 2023 am 09:33 AM
How to use JS and Baidu Maps to implement the map heat map function Introduction: With the rapid development of the Internet and mobile devices, maps have become a common application scenario. As a visual display method, heat maps can help us understand the distribution of data more intuitively. This article will introduce how to use JS and Baidu Map API to implement the map heat map function, and provide specific code examples. Preparation work: Before starting, you need to prepare the following items: a Baidu developer account, create an application, and obtain the corresponding AP
PHP and JS Development Tips: Master the Method of Drawing Stock Candle Charts
Dec 18, 2023 pm 03:39 PM
With the rapid development of Internet finance, stock investment has become the choice of more and more people. In stock trading, candle charts are a commonly used technical analysis method. It can show the changing trend of stock prices and help investors make more accurate decisions. This article will introduce the development skills of PHP and JS, lead readers to understand how to draw stock candle charts, and provide specific code examples. 1. Understanding Stock Candle Charts Before introducing how to draw stock candle charts, we first need to understand what a candle chart is. Candlestick charts were developed by the Japanese
The relationship between js and vue
Mar 11, 2024 pm 05:21 PM
The relationship between js and vue: 1. JS as the cornerstone of Web development; 2. The rise of Vue.js as a front-end framework; 3. The complementary relationship between JS and Vue; 4. The practical application of JS and Vue.
