js数据结构-二进制树（二进制搜索树）

可能有些人没有读我在上一篇文章中写的二进制叉，所以在这里我复制了二进制树的基本概念. 如果已阅读过，则可以忽略先前对二叉树基本概念的介绍. 如果数据结构不清楚，最好看看我写的链表的js数据结构

二叉树（Binary Tree）是一种树结构. 其特征是每个节点最多具有两个分支节点. 二叉树通常由根节点，分支节点和叶节点组成. 每个分支节点通常称为子树.

常用条款

在二叉树中，我们经常使用父节点和子节点来描述，例如，图中的2是6和3的父节点，否则6和3是2个子节点

在二叉树的第i层，最多有2个^ i-1个节点

深度为k的二叉树最多具有2 ^ k-1个节点

对于任何二叉树T，如果点的总和为n0且度为2的节点数（子树的数量为2）为n2，则n0 = n2 +1

二叉树分为完整的二叉树（完整的二叉树）和完整的二叉树（完整的二叉树）

二进制搜索树满足以下属性:

让我们举个例子来深入了解以下内容

一组数据: 12、4、18、1、8、16、20

从下图可以看到，左图满足二叉树的性质. 每个左子节点均小于父节点，右子节点均大于其父节点，左子树节点均小于根节点. 右子树的节点大于根节点

二分搜索树的主要操作:

从下图可以看出，二叉搜索树的节点通常包含4个字段，即数据元素，由指向其左右节点的指针和指向父节点的指针组成. 这种存储结构通常称为“三叉链表”.

使用代码初始化二进制搜索树的节点:

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

接下来，我们使用代码初始化二进制搜索树

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

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

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

与根节点12相比，它大于12，因此我们确定此节点已插入右侧子树中，并且根节点右侧已经存在一个节点，然后与该节点18进行比较二叉查找树 二叉排序树，结果小于18. 18的左节点找到一个位置，而18的左节点已经有一个节点，因此继续与该节点进行比较，结果小于16并且16的左节点为空（left = null），因此将13节点插入到16的左节点

通过上面的描述，让我们看看如何编写代码

    insert(node){
        let p = this.root;
        let tail = this.root;
        
        // 循环遍历，去找到对应的位置
        while(tail) {
            p = tail;
            // 要插入的节点key比当前节点小
            if (node.key < tail.key){
                tail = tail.left;
            }
            // 要插入的节点key比当前节点大
            else {
                tail = tail.right;
            }
        }
        
        // 没有根节点，则直接作为根节点插入
        if(!p) {
            this.root = node;
            return;
        }
        
        // p是最后一个节点，也就是我们要插入的位置的父节点
        // 比父节点大则往右边插入
        if(p.key < node.key){
            p.right = node;
        }
        // 比父节点小则往左边插入
        else {
            p.left = node;
        }
        
        // 指向父节点
        node.parent = p;
    }

搜索非常简单. 实际上，它与插入有很大不同. 它们全部达到左右节点的大小，然后向下看

    search(key) {
        let p = this.root;
        if(!p) {
            return;
        }
        
        while(p && p.key !== key){
            if(p.key<key){
                p = p.right;
            }else{
                p = p.left;
            }
        }
        
        return p;
    }

最常用的是中间顺序遍历，因为中间顺序遍历可以获取已排序的列表，这就是为什么使用二叉搜索树进行排序的原因

根据以上对中阶遍历的解释，代码变得非常简单，这是一个递归过程，而递归停止的条件是该节点为空

    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，所以输出仅为4、12、18

补充: 在此位置使用了Generator，因此它返回一个迭代器. 您可以通过以下方式获得有序数组，前提是已经有插入的节点

   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 < key) {
        p = p.right;
      } else {
        p = p.left;
      }
    }
    return p;
  }
  insert(node) {
    // 尾指针的父节点指针
    let p = this.root;
    // 尾指针
    let tail = this.root;
    while (tail) {
      p = tail;
      if (node.key < tail.key) {
        tail = tail.left;
      } else {
        tail = tail.right;
      }
    }
    if (!p) {
      this.root = node;
      return;
    }
    // 插入
    if (p.key < node.key) {
      p.right = node;
    } else {
      p.left = node;
    }
    node.p = p;
  }
  transverse() {
    return this.__transverse(this.root);
  }
  *__transverse(node) {
    if (!node) {
      return;
    }
    yield* this.__transverse(node.left);
    yield node;
    yield* this.__transverse(node.right);
  }
}

二进制搜索树完成. 实际上，这与链接列表非常相似. 它仍然操作一些指针. 由于它被称为搜索树二叉查找树 二叉排序树，因此主要用于左搜索. 也有排序. 现在，如果您已大致了解二进制搜索树中的最大值和最小值，也很方便.

我对撰写本文感到有些混乱，因为我总是觉得引言不适当，因此一些基础较差的人不会理解它. 如果有一些不理解的地方或文章有误，请发表评论. <

接下来要写什么，我也在思考这个问题，排序算法，第三方反应的一些模拟实现？ ，是一个小程序组件库吗？还是别的，让我再考虑几个小时，因为是的，有建议的朋友也可以留言说哈.

最后，最重要的是给个赞，请扇动一下，谢谢

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-224399-1.html