Definition and usage examples of JavaScript binary search tree

This article mainly introduces the definition and representation method of the binary search tree of JavaScript data structure. It briefly describes the concept and characteristics of the binary search tree and the creation, insertion, traversal and other operations of the binary search tree in JavaScript. For implementation tips, friends in need can refer to

This article explains the definition and representation method of the binary search tree of JavaScript data structure through examples. Share it with everyone for your reference, the details are as follows:

Tree is a non-linear data structure that stores data in a hierarchical manner. Trees are used to store data with hierarchical relationships, such as files in a file system; trees are also used to store ordered lists. A special kind of tree will be studied here: the binary tree. Trees were chosen over those basic data structures because searching on a binary tree is very fast (while searching on a linked list is not), and adding or removing elements from a binary tree is also very fast (while adding or removing an element from an array is not) so).

A tree is a finite set of n nodes. The top is the root, and the bottom is the subtree of the root. A tree node contains a data element and branches pointing to its subtrees. The subtree owned by a node is called the degree of the node. Nodes with degree 0 are called leaves or terminal nodes. Nodes with a degree other than 0 are called non-terminal nodes or branch nodes. The degree of the tree is the maximum value of the degree of each node in the tree. The hierarchy of nodes is defined starting from the root, which is level 0. The maximum level of nodes in the tree is called the depth or height of the tree.

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

Before using JavaScript to build a binary tree, we need to add two new terms to our dictionary about trees. The two child nodes of a parent node are called left node and right node respectively. In some implementations of binary trees, 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 ​​are stored in the right node. This feature makes searches very efficient, both for numeric and non-numeric data, such as words and strings.

The binary search tree is composed of nodes, so we need to define a Node object. The code is as follows:

function Node(data,left,right){//结点类
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}
function show(){//显示节点中数据
    return this.data;
}

where left and right are used to point to the left and right respectively. child node.

Next, you need to create a binary search tree class. The code is as follows:

function BST(){//树类
    this.root=null;
    this.insert=insert;
    this.inOrder=inOrder;
    this.preOrder=preOrder;
    this.postOrder=postOrder;
}

The next step is the code to insert the node. Traverse the small ones and insert them on the left, and the big ones on the right. The code is as follows:

function insert(data){//插入操作
    var n=new Node(data,null,null);
    if(this.root==null){//第一个元素
      this.root=n;
    }else{
      var current=this.root;//永远指向根节点
      var parent;
      while(true){//一直运行直到找到左结点或右结点为止
        parent=current;
        if(data<current.data){
          current=current.left;
          if(current==null){//如果没有左节点
            parent.left=n;
            break;
          }
        }else{
          current=current.right;
          if(current==null){//如果没有右节点
            parent.right=n;
            break;
          }//如果有右节点，则跳到while重新执行，将该节点作为parent重新开始判断
        }
      }
    }
}

The above is the detailed content of Definition and usage examples of JavaScript binary search tree. For more information, please follow other related articles on the PHP Chinese website!