Detailed introduction to JavaScript binary trees (binary search trees)

This article brings you a detailed introduction to JavaScript binary trees (binary search trees). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

There may be some people who have not read the binary heap I wrote in my last article, so the basic concept of binary tree is copied here. If you have read it, you can ignore it. The previous introduction to the basic concepts of binary trees. In addition, if you are not clear about the linked list data structure, it is best to take a look at the js data structure I wrote before - linked list

binary tree

Binary Tree (Binary Tree) is A tree structure characterized by that each node has at most two branch nodes. A binary tree usually consists of a root node, branch nodes, and leaf nodes. Each branch node is often called a subtree.

• Root node: the top node of the binary tree

• Branch node: In addition to the root node and has leaf nodes

• Leaf node: except itself, has no other child nodes

Common terms
In a binary tree, we often use parent nodes and child nodes to describe it. For example, 2 in the figure is the parent node of 6 and 3, and conversely 6 and 3 are the child nodes of 2

Three properties of binary trees

1. On the i-th level of the binary tree, there are at most 2^i-1 nodes

• When i=1, only A root node, 2^(i-1) = 2^0 = 1

A binary tree with depth k has at most 2^k-1 nodes

• #i=2, 2^k-1 = 2^2 - 1 = 3 nodes

For any tree Binary tree T, if the number of summary points is n0 and the number of nodes with degree 2 (number of subtrees is 2) is n2, then n0=n2 1

Three main differences between trees and binary trees

• The number of nodes in a tree is at least 1, while the number of nodes in a binary tree can be 0

• The maximum degree of nodes in the tree (node There is no limit on the number), while the maximum degree of a node in a binary tree is 2

• The nodes of the tree are not divided into left and right, while the nodes of the binary tree are divided into left and right

Binary tree classification

Binary trees are divided into complete binary trees and full binary trees

• Full binary trees: a tree with a depth of k And a binary tree with 2^k - 1 nodes is called a full binary tree

• Complete binary tree: A complete binary tree means that the left side of the last layer is full, and the right side may be full or not full, and then A binary tree in which the remaining levels are full is called a complete binary tree (a full binary tree is also a complete binary tree)

Binary search Tree

Binary search tree satisfies the following properties:

• If the left subtree of any node is not empty, then the values ​​of all nodes on the left subtree are equal Less than the value of its root node;

• If the right subtree of any node is not empty, then the values ​​of all nodes on the right subtree are greater than the value of its root node;

• The left and right subtrees of any node also need to satisfy the property that the left is small and the right is large

Let’s give an example to understand the following

A set of data: 12,4,18,1,8,16,20
As can be seen from the figure below, the figure on the left satisfies the properties of a binary tree. Each of its left child nodes is smaller than the parent node, the right child node is greater than its parent node, at the same time, the nodes of the left subtree are less than the root node, and the nodes of the right subtree are greater than the root node

The main operations of binary search tree:

• Search

• Insert

• Traverse (transverse)

The chained storage structure of the binary search tree

Through the following figure, you can know that the nodes of the binary search tree usually contain 4 Each field and data element is composed of pointers pointing to its left and right nodes respectively and a pointer pointing to the parent node. This storage structure is generally called a three-way linked list.

Use code to initialize the node of a binary search tree:

• A pointer to the parent node parent

• A pointer to the left node left

• A pointer to the right node right

• a Data element, which can be a key and value

    class BinaryTreeNode {
        constructor(key, value){
            this.parent = null;
            this.left = null;
            this.right = null;
            this.key = key;
            this.value = value;
        }
    }

Then we use code to initialize a binary search tree

• 在二叉搜索树中我们会维护一个root指针，这个就相当于链表中的head指针，在没有任何节点插入的时候它指向空，在有节点插入以后它指向根节点。

    class BinarySearchTree {
        constructor() {
            this.root = null;
        }
    }

创建节点

    static createNode(key, value) {
        return new BinarySearchTree(key, value);
    }

插入操作

看下面这张图，13是我们要插入的节点，它插入的具体步骤：

1. 跟根节点12做比较，比12大，所以我们确定了，这个节点是往右子树插入的

2. 而根节点的右边已经有节点，那么跟这个节点18做比较，结果小于18所以往18的左节点找位置

3. 而18的左节点也已经有节点了，所以继续跟这个节点做比较，结果小于16

4. 刚好16的左节点是空的(left=null)，所以13这个节点就插入到了16的左节点

通过上面的描述，我们来看看代码是怎么写的

• 定义两个指针，分别是p和tail，最初都指向root，p是用来指向要插入的位置的父节点的指针，而tail是用来查找插入位置的，所以最后它会指向null，用上图举个例子，p最后指向了6这个节点，而tail最后指向了null（tail为null则说明已经找到了要插入的位置）

• 循环，tail根据我们上面分析的一步一步往下找位置插入，如果比当前节点小就往左找，大则往右找，一直到tail找到一个空位置也就是null

• 如果当前的root为null，则说明当前结构中并没有节点，所以插入的第一个节点直接为跟节点，即this.root = node

• 将插入后的节点的parent指针指向父节点

    insert(node){
        let p = this.root;
        let tail = this.root;
        
        // 循环遍历，去找到对应的位置
        while(tail) {
            p = tail;
            // 要插入的节点key比当前节点小
            if (node.key <h3>查找</h3><p>查找就很简单了，其实和插入差多，都是去别叫左右节点的大小，然后往下找</p>

• 如果root = null, 则二叉树中没有任何节点，直接return，或者报个错什么的。

• 循环查找

    search(key) {
        let p = this.root;
        if(!p) {
            return;
        }
        
        while(p && p.key !== key){
            if(p.key<key><h3>遍历</h3>
<ul class=" list-paddingleft-2">
<li><p>中序遍历(inorder)：先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表</p></li>
<li><p>前序遍历(preorder)：先自己，再遍历左节点，最后遍历右节点</p></li>
<li><p>后序遍历(postorder)：先左节点，再右节点，最后自己</p></li>
</ul>
<p>最常用的一般是中序遍历，因为中序遍历可以得到一个已经排好序的列表，这也是为什么会用二叉搜索树排序的原因</p>
<p>根据上面对中序遍历的解释，那么代码就变的很简单，就是一个递归的过程，递归停止的条件就是节点为null</p>
<ul class=" list-paddingleft-2">
<li><p>先遍历左节点-->yield* this._transverse(node.left)</p></li>
<li><p>遍历自己 --> yield* node</p></li>
<li><p>遍历左节点 --> yield* this._transverse(node.right)</p></li>
</ul>
<pre class="brush:php;toolbar:false">    transverse() {
        return this._transverse(this.root);
    }
    
    *_transverse(node){
        if(!node){
            return;
        }
        yield* this._transverse(node.left);
        yield node;
        yield* this._transverse(node.right)
    }

看上面这张图，我们简化的来看一下，先访问左节点4，再自己12，然后右节点18，这样输出的就刚好是一个12，4，8

补充：这个地方用了generater，所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组，这里的前提就当是已经有插入的节点了

   const tree = new BinaryTree();
   //...中间省略插入过程
    
   // 这样就返回了一个有序的数组 
   var arr = [...tree.transverse()].map(item=>item.key);

完整代码

class BinaryTreeNode {
  constructor(key, value) {
    // 指向父节点
    this.p = null;

    // 左节点
    this.left = null;

    // 右节点
    this.right = null;

    // 键
    this.key = key;

    // 值
    this.value = value;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  static createNode(key, value) {
    return new BinaryTreeNode(key, value);
  }

  search(key) {
    let p = this.root;
    if (!p) {
      return;
    }

    while (p && p.key !== key) {
      if (p.key <h3>总结</h3><p>二叉查找树就讲完了哈，其实这个和链表很像的，还是操作那么几个指针，既然叫查找树了，它主要还是用来左一些搜索，还有就是排序了，另外补充一下，二叉查找树里找最大值和最小值也很方便是不是，如果你大致读懂了的话。</p><p class="comments-box-content"></p>

The above is the detailed content of Detailed introduction to JavaScript binary trees (binary search trees). For more information, please follow other related articles on the PHP Chinese website!