Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to define the binary search tree in JavaScript". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Tree is a non-linear data structure, which stores data in a hierarchical way. Trees are used to store hierarchical data, such as files in the file system, and trees are used to store ordered lists. Here we will study a special kind of tree: binary tree. Trees are chosen over basic data structures because lookups on binary trees are very fast (but not on linked lists). It is also very fast to add or remove elements to a binary tree (not to add or delete an array).

A tree is a finite set of n nodes. The top is the root, and the bottom is the subtree of the root. The node of a tree contains a data element and several branches that point to its subtree. The subtree owned by a node is called the degree of the node. A node with degree 0 is called a leaf or terminal node. A node whose degree is not zero is called a non-terminal node or a branch node. The degree of the tree is the maximum of the degree of each node in the tree. The hierarchy of nodes is defined from the root, and the root is layer 0. The maximum level of nodes in a tree is called the depth or height of the tree.

Binary tree is a special tree with no more than two child nodes. Binary trees have some special computational properties, which make some operations on them extremely efficient. By limiting the number of child nodes to 2, you can write efficient programs to insert, find, and delete data in the tree.

Before using JavaScript to build a binary tree, we need to add two new nouns to our dictionary about trees. The two children of a parent node are called the left node and the right node, respectively. In some binary tree implementations, the left node contains a specific set of values and the right node contains another specific set of values. Binary search tree is a special binary tree, in which relatively small values are stored in the left node and larger values in the right node. This feature makes lookup efficient, both for numeric and non-numeric data, such as words and strings.

The binary search tree consists of nodes, so we define a Node object with the following code:

Function Node (data,left,right) {/ / Node class this.data=data; this.left=left; this.right=right; this.show=show;} function show () {/ / display the data in the node return this.data;}

Left and right are used to point to the left and right child nodes, respectively.

Next, you need to create the class of the binary lookup tree, as follows:

Function BST () {/ / tree class this.root=null; this.insert=insert; this.inOrder=inOrder; this.preOrder=preOrder; this.postOrder=postOrder;}

Next is the code to insert the node. Go through the small ones on the left and the big ones on the right. The code is as follows:

Function insert (data) {/ / insert operation var n=new Node (data,null,null); if (this.root==null) {/ / first element this.root=n;} else {var current=this.root;// always points to the root node var parent; while (true) {/ / until the left or right node is found parent=current; if (data

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.