JS数据结构与算法-二叉树和二叉查找树-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

JS数据结构与算法-二叉树和二叉查找树

简介: 树是一种非线性的数据结构,以分层的方式存储数据。树被用来存储具有层级关系的结构,比如文件系统中的文件;树还被用来存储有序列表。 二叉树与二叉查找树二叉树是一种特殊的树,它的子节点个数不超过两个;一个父节点的两个子节点分别称为左节点和右节点。

树是一种非线性的数据结构,以分层的方式存储数据。树被用来存储具有层级关系的结构,比如文件系统中的文件;树还被用来存储有序列表。

  1. 二叉树与二叉查找树
    二叉树是一种特殊的树,它的子节点个数不超过两个;一个父节点的两个子节点分别称为左节点和右节点。
    二叉查找树(BST)是一种特殊的二叉树;相对较小的值保持在左节点中,较大的值保存在右节点中。

  2. js代码实现二叉查找树

  • 首先我们先定义一个Node对象,用于保存数据(data),也保存和其他节点的链接(left和right)。
function Node(data,left,right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
  • 定义show方法
function show() {
  return this.data;
}
  • 创建一个类,用来表示二叉查找树(BST)
function BST() {
  //将根节点初始化为null
  this.root = null;
  //insert方法用来向树中加入新节点
  this.insert = insert;
  //inOrder方法用来遍历树
  this.inOrder = inOrder;
}
  • 定义insert方法
function insert(data) {
  //首先实例化一个新的Node对象
  var n = new Node(data,null,null);
  //检查BST是否有根节点,如果没有,那么是颗新树,传入的该节点就是根节点
  if(this.root == null) {
    this.root = n;
  }else {
    //反之就定义一个current变量用于保存当前节点(根节点)
    var current = this.root;
    var parent;
    while(true) {
      parent = current;
      //如果插入的节点保存的数据小于当前节点,且当前节点的左节点为null,就将这个新的节点插入到这个位置
      if(data < current.data) {
        current = current.left;
        if(current == null) {
          parent.left = n;
          break;
        }
      }else {
        //反之,同理
        current = current.right;
        if(current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}
  1. 遍历二叉查找树
    有三种遍历BST的方式
    中序:中序遍历按照节点上的键值,以升序访问BST上的所有节点。
    先序:先序遍历先访问根节点,然后以同样的方式访问左子树和右子树。
    后序:后序遍历先访问叶子节点(没有任何子节点的节点),从左子树到右子树,再到根节点。
    这三种遍历理解了一种的实现代码,其他的都好理解,所以我着重写一下我对js代码实现中序遍历过程的具体理解。
  • js代码实现中序遍历
    中序遍历使用递归的方式,以升序访问树中所有节点,先访问左子树,在访问根节点,最后访问右子树。
function inOrder(node) {
  if(!(node == null)) {
    inOrder(node.left);
    console.log(node.show());
    inOrder(node.right);      
  }
}
//比如:
var nums = new BST();
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);

inOrder(nums.root); //10 22 30 56 81 77 92

①先递归遍历左子树到尽头,将每一项push到一个数组中,先是得到这样的一个结果[56,22,10]。

②递归完成了,现在pop出第一项即10开始遍历右子树,为undefined。

③然后pop出第二项即22,遍历右子树,得30,因为console是在先递归左子树后打印的,所以把30插到(push)56和22中间,结果为[56,30,22,10]。

④然后pop出第三项即30,undefined。

⑤然后pop出第四项即56,遍历该右子树,得结果[92,81,56,30,22,10]

⑥然后pop出第五项即81,发现有左子树77,所以push进去,又因为console代码在中间,所以要放到92和81中间,结果[92,81,77,56,30,22,10]所以最后打印结果为10,22,30,56,77,81,92

理解了一个,后面的先序遍历和后序遍历就没问题了,只是console代码放置的位置不同。主要是理解递归。

  • 先序遍历
function inOrder(node) {
  if(!(node == null)) {
    console.log(node.show());
    inOrder(node.left);
    inOrder(node.right);      
  }
}
inOrder(nums.root);
  • 后序遍历
function inOrder(node) {
  if(!(node == null)) {
    inOrder(node.left);
    inOrder(node.right);      
    console.log(node.show());
  }
}
inOrder(nums.root);

参考学习

《数据结构与算法JavaScript描述》
《高程》

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章