关于JavaScript二叉树的详细介绍

发布时间:2020-07-08 14:29:08 作者:Leah
来源:亿速云 阅读:163

本篇文章给大家分享的是有关关于JavaScript二叉树的详细介绍,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

可能有一部分人没有读过我上一篇写的二叉堆,所以这里把二叉树的基本概念复制过来了,如果读过的人可以忽略前面针对二叉树基本概念的介绍,另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表

二叉树

二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。

关于JavaScript二叉树的详细介绍

常用术语
在二叉树中,我们常常还会用父节点和子节点来描述,比如图中2为6和3的父节点,反之6和3是2子节点

二叉树的三个性质

  1. 在二叉树的第i层上,至多有2^i-1个节点

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

  3. 对任何一棵二叉树T,如果总结点数为n0,度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要差别

二叉树分类

二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

关于JavaScript二叉树的详细介绍

二叉搜索树

二叉搜索树满足以下的几个性质:

我们来举个例子来深入理解以下

一组数据:12,4,18,1,8,16,20
由下图可以看出,左边的图满足了二叉树的性质,它的每个左子节点都小于父节点,右子节点大于其父节点,同时左子树的节点都小于根节点,右子树的节点都大于根节点

关于JavaScript二叉树的详细介绍

二叉搜索树主要的几个操作:

二叉树搜索树的链式存储结构

通过下图,可以知道二叉搜索树的节点通常包含4个域,数据元素,分别指向其左,右节点的指针和一个指向父节点的指针所构成,一般把这种存储结构称为三叉链表。
关于JavaScript二叉树的详细介绍cdn.segmentfault.com/v-5c2db555/global/img/squares.svg">

用代码初始化一个二叉搜索树的结点:

    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是我们要插入的节点,它插入的具体步骤:

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

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

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

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

关于JavaScript二叉树的详细介绍

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

    insert(node){
        let p = this.root;
        let tail = this.root;
        
        // 循环遍历,去找到对应的位置
        while(tail) {
            p = tail;
            // 要插入的节点key比当前节点小
            if (node.key < tail.key){
                tail.left = tail.left;
            }
            // 要插入的节点key比当前节点大
            else {
                tail.right = 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;
    }

遍历

最常用的一般是中序遍历,因为中序遍历可以得到一个已经排好序的列表,这也是为什么会用二叉搜索树排序的原因

根据上面对中序遍历的解释,那么代码就变的很简单,就是一个递归的过程,递归停止的条件就是节点为null

    transverse() {
        return this._transverse(this.root);
    }
    
    *_transverse(node){
        if(!node){
            return;
        }
        yield* this._transverse(node.left);
        yield node;
        yield* this._transverse(node.right)
    }

关于JavaScript二叉树的详细介绍

看上面这张图,我们简化的来看一下,先访问左节点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 < 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);
  }
}

总结

二叉查找树就讲完了哈,其实这个和链表很像的,还是操作那么几个指针,既然叫查找树了,它主要还是用来左一些搜索,还有就是排序了,另外补充一下,二叉查找树里找最大值和最小值也很方便是不是,如果你大致读懂了的话。

以上就是关于JavaScript二叉树的详细介绍,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。

推荐阅读:
  1. Ajax的详细介绍
  2. JavaScript中关于作用域的详细介绍

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

数据结构和算法 数据结构 node.js

上一篇:Docker入门与应用实战之容器网络

下一篇:TFS中的迭代(五)

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》