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

2017-08-31 本文已影响136人 ComfyUI

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

二叉树与二叉查找树
二叉树是一种特殊的树，它的子节点个数不超过两个；一个父节点的两个子节点分别称为左节点和右节点。
二叉查找树(BST)是一种特殊的二叉树；相对较小的值保持在左节点中，较大的值保存在右节点中。
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;
        }
      }
    }
  }
}

遍历二叉查找树
有三种遍历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描述》
《高程》

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

猜你喜欢

热点阅读