JS数据结构和算法-二叉树和二叉搜索树

树是一种非线性数据结构，以分层方式存储数据. 树用于存储具有层次关系的结构，例如文件系统中的文件. 树还用于存储有序列表.

二叉树和二叉搜索树

二叉树是一种特殊的树，其子节点的数量不超过两个；父节点的两个子节点分别称为左节点和右节点.

二叉搜索树（BST）是一种特殊的二叉树. 相对较小的值保留在左侧节点中，较大的值保留在右侧节点中.

js代码实现了二进制搜索树

function Node(data,left,right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

function show() {
  return this.data;
}

function BST() {
  //将根节点初始化为null
  this.root = null;
  //insert方法用来向树中加入新节点
  this.insert = insert;
  //inOrder方法用来遍历树
  this.inOrder = inOrder;
}

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;
        }
      }
    }
  }
}

遍历二进制搜索树

有三种遍历BST的方式

中间顺序: 中间顺序遍历根据节点上的键值以升序访问BST上的所有节点.

预订: 首先访问根节点，然后以相同的方式访问左右子树.

后序: 后序遍历首先访问叶节点（没有任何子节点的节点），从左子树到右子树，再到根节点.

这三种遍历可以理解一种实现代码，而其他两种则很容易理解，因此我将在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

①首先递归地遍历左子树到最后，将每个项目推入数组，首先得到这样的结果[56,22,10].

②递归完成，现在弹出的第一项，即10，开始遍历未定义的右侧子树.

③然后弹出第二个项目22，以遍历右边的子树，得到30，因为首先在递归左边的子树后打印了控制台，所以在（推）56和22之间插入了30，结果是[56,30,22,10].

④然后弹出未定义的第三项，即30.

⑤然后弹出第四项二叉排序树算法，即56，并遍历右侧子树以得到结果[92,81,56,30,22,10]

⑥然后弹出第五项81，发现有一个左子树77二叉排序树算法，因此将其推入，由于控制台代码在中间，因此必须将其放在92和81之间，结果[ 92,81,77,56，30,22,10]最终的打印结果是10,22,30,56,77,81,92

了解一下，一阶遍历和二阶遍历没有问题，但是控制台代码放置在不同的位置. 主要是了解递归.

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描述”

“海拔”

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