JavaScript二叉树(二叉搜索树)的详细介绍

夏枫君_5184

夏枫君_5184

2019-01-08

3316人浏览

转载

本篇文章给大家带来的内容是关于javascript二叉树(二叉搜索树)的详细介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

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

二叉树

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

bVbmEdC.png

  • 根节点:二叉树最顶层的节点

  • 分支节点:除了根节点以外且拥有叶子节点

  • 叶子节点:除了自身,没有其他子节点

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

二叉树的三个性质

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

  • i=1时,只有一个根节点,2^(i-1) = 2^0 = 1

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

    • i=2时,2^k-1 = 2^2 - 1 = 3个节点

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

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

    • 树的节点个数至少为1,而二叉树的节点个数可以为0

    • 树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2

    • 树的节点没有左右之分,而二叉树的节点有左右之分

    二叉树分类

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

    • 满二叉树:一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树

    • 完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

    bVbmEH7.png

    二叉搜索树

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

    • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

    • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

    • 任意节点的左、右子树也需要满足左边小右边大的性质

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

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

    2264746377-5c3303126cf52_articlex.png

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

    • 查找(search)

    • 插入(insert)

    • 遍历(transverse)

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

    通过下图,可以知道二叉搜索树的节点通常包含4个域,数据元素,分别指向其左,右节点的指针和一个指向父节点的指针所构成,一般把这种存储结构称为三叉链表。
    图片描述

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

    • 一个指向父亲节点的指针 parent

      JavaScript规范工具(免费版)
      JavaScript规范工具(免费版)

      面向个人开发者的JavaScript代码风格指南,涵盖核心规则与基础代码审查能力。

      下载
    • 一个指向左节点的指针 left

    • 一个指向右节点的指针 right

    • 一个数据元素,里面可以是一个key和value

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

    接着我们再用代码去初始化一个二叉搜索树

    • 在二叉搜索树中我们会维护一个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的左节点

    995916720-5c3219c38a4eb_articlex.png

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

    • 定义两个指针,分别是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)
        }

    496773676-5c33075897e72_articlex.png

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

    Java免费学习笔记:立即使用
    解锁 Java 大师之旅:从入门到精通的终极指南

    相关文章

    java速学教程(入门到精通)
    java速学教程(入门到精通)

    java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

    下载

    相关标签:

    node.js javascript

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

    相关专题

    更多
    Navicat创建数据库教程
    Navicat创建数据库教程

    本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

    2026.11.20

    0

    7

    Navicat入门教程大全
    Navicat入门教程大全

    本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

    2026.11.20

    0

    17

    Navicat数据库连接配置指南
    Navicat数据库连接配置指南

    从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

    2026.11.20

    0

    10

    PHP8.6数组与数据处理教程
    PHP8.6数组与数据处理教程

    本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

    2026.11.20

    0

    8

    PHP8.6升级迁移教程
    PHP8.6升级迁移教程

    本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

    2026.11.20

    0

    10

    PHP8.6安装配置与FPM运维教程
    PHP8.6安装配置与FPM运维教程

    本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

    2026.11.20

    0

    10

    Nginx CVE-2026-123007排查与防护指南
    Nginx CVE-2026-123007排查与防护指南

    Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

    2026.11.20

    20

    8

    GoFrame框架Web开发与路由中间件
    GoFrame框架Web开发与路由中间件

    本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

    2026.11.17

    60

    15

    GoFrame框架安装与gf命令行工具
    GoFrame框架安装与gf命令行工具

    本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

    2026.11.17

    80

    15

    热门下载

    更多
    网站特效
    /
    网站源码
    /
    网站素材
    /
    前端模板

    精品课程

    更多
    相关推荐
    /
    热门推荐
    /
    最新课程
    LLVM Programmer’s Manual
    LLVM Programmer’s Manual

    共0课时 | 0人学习

    MongoDB 教程
    MongoDB 教程

    共17课时 | 6.6万人学习