JS实现二叉查找树的建立以及一些遍历方法实现_网络技术

JS实现二叉查找树的建立以及一些遍历方法实现

发布时间 - 2026-01-11 00:40:55 点击率：次

二叉查找树是由节点和边组成的。

我们可以定义一个节点类Node，里面存放节点的数据，及左右子节点，再定义一个用来显示数据的方法：

//以下定义一个节点类
function Node(data,left,right){
  // 节点的键值
  this.data = data;
  // 左节点
  this.left = left;
  // 右节点
  this.right = left;
  // 显示该节点的键值
  this.show = show;
}
// 实现show方法
function show(){
  return this.data;
}

再定义一个二叉查找树类BST，该类中有定义树的根节点，初始化为null，然后定义插入节点的方法，还有一边遍历的方法：

// 二叉查找树BST
// 有一个节点属性，还有一些其他的方法，以下定义一个二叉查找树BST类
function BST(){
  // 根节点初始化为空
  this.root = null;
  // 方法
  // 插入
  this.insert = insert;
  // 中序遍历
  this.inorder = inorder;
  // 先序遍历
  this.preorder = preorder;
  // 后序遍历
  this.postorder = postorder;
}

//实现insert插入方法
function insert(data){
  // 创建一个节点保存数据
  var node = new Node(data,null,null);
  // 下面将节点node插入到树中
  // 如果树是空的，就将节点设为根节点
  if(!this.root){
    this.root = node;
  }else{ //树不为空
    // 判断插在父节点的左边还是右边
    // 所以先要保存一下父节点
    // var parent = this.root;
    var current = this.root;
    var parent;
    // 如果要插入的节点键值小于父节点键值，则插在父节点左边，
    // 前提是父节点的左边为空，否则要将父节点往下移一层，
    // 然后再做判断
    while(true){
      // data小于父节点的键值
      parent = current;
      if(data < parent.data){
        // 将父节点往左下移(插入左边)
        // parent = parent.left;
        current = current.left;
        // 如果节点为空，则直接插入
        if(!current){
          // ！！！此处特别注意，如果就这样把parent赋值为node，也仅仅只是parent指向node，
          // 而并没有加到父元素的左边！！！根本没有加到树中去。所以要先记住父元素，再把当前元素加入进去
          parent.left = node;
          break;
        }      
      }else{ // 将父节点往右下移(插入右边)
        current = current.right;
        if(!current){
          parent.right = node;
          break;
        }
      }
    }

  }
} 

//实现inorder遍历方法(左中右)
function inorder(node){
  if(node){
    inorder(node.left);
    console.log(node.show());
    inorder(node.right);
  }
}

// 先序遍历(中左右)
function preorder(node){
  if(node){
    console.log(node.show());
    preorder(node.left);
    preorder(node.right);
  }
}

// 后序遍历(左右中)
function postorder(node){
  if(node){
    preorder(node.left);
    preorder(node.right);
    console.log(node.show());
  }
}

测试：

// 后序遍历(左右中)
function postorder(node){
  if(node){
    postorder(node.left);
    postorder(node.right);
    console.log(node.show());
  }
}

// 实例化一个BST树
var tree = new BST();
// 添加节点
tree.insert(30);
tree.insert(14);
tree.insert(35);
tree.insert(12);
tree.insert(17);
// 中序遍历
tree.inorder(tree.root);
// 先序遍历
tree.preorder(tree.root);
// 后序遍历
tree.postorder(tree.root);

结果：

中序遍历：

先序遍历：

后序遍历：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# JS实现二叉查找树 # js # 二叉查找树 # js实现二叉树 # JavaScript数据结构之二叉查找树的定义与表示方法 # JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例 # JavaScript实现二叉树定义、遍历及查找的方法详解 # JavaScript数据结构之二叉树的查找算法示例 # JS实现的二叉树算法完整实例 # JavaScript实现二叉树的先序、中序及后序遍历方法详解 # javascript实现二叉树遍历的代码 # Javascript实现从小到大的数组转换成二叉搜索树 # JavaScript数据结构之二叉树的删除算法示例 # JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】 # JavaScript数据结构之二叉树的遍历算法示例 # JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解 # 遍历 # 键值 # 为空 # 插在 # 是由 # 中有 # 设为 # 其他的 # 我们可以 # 要将 # 要先 # 就将 # 中去 # 往下 # 还有一些 # 再把 # 再做 # 创建一个 # 值为 # 大家多多

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：如何在Windows主机上安装和配置WordPress等CM

下一篇：Thinkphp5.1趣味实现学生扫码选座功能

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：如何在Windows主机上安装和配置WordPress等CM

下一篇：Thinkphp5.1趣味实现学生扫码选座功能