DDR爱好者之家

JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解
站长资源 2024/11/25 佚名
61 1538
DDR爱好者之家 Design By 杰米

本文实例讲述了JS中的算法与数据结构之二叉查找树（Binary Sort Tree）。分享给大家供大家参考，具体如下：

二叉查找树（Binary Sort Tree）

我们之前所学到的列表，栈等都是一种线性的数据结构，今天我们将学习计算机中经常用到的一种非线性的数据结构——树（Tree），由于其存储的所有元素之间具有明显的层次特性，因此常被用来存储具有层级关系的数据，比如文件系统中的文件；也会被用来存储有序列表等。

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根（root）。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。一个结点所拥有的子结点的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树

二叉树是一种特殊的树，它的子节点个数不超过两个，且分别称为该结点的左子树（left subtree）与右子树（right subtree），二叉树常被用作二叉查找树和二叉堆或是二叉排序树（BST）。

JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解 
二叉树

按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次，这个操作被称为树的遍历，是对树的一种最基本的运算。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

按照根节点访问的顺序不同，树的遍历分为以下三种：前序遍历，中序遍历，后序遍历；

前序遍历：根节点->左子树->右子树

JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解 
先序遍历

中序遍历：左子树->根节点->右子树

JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解 
中序遍历

后序遍历：左子树->右子树->根节点

JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解 
后序遍历

因此我们可以得之上面二叉树的遍历结果如下：前序遍历：ABDEFGC 中序遍历：DEBGFAC 后序遍历：EDGFBCA

二叉查找树（BST）

实际应用中，树的每个节点都会有一个与之相关的值对应，有时候会被称为键。因此，我们在构建二叉查找树的时候，确定子节点非常的重要，通常将相对较小的值保存在左节点中，较大的值保存在右节点中，这就使得查找的效率非常高，因此被广泛使用。

二叉查找树的实现

根据上面的知识，我们了解到二叉树实际上是由多个节点组成，因此我们首先就要定义一个Node类，用于存放树的节点，其构造与前面的链表类似。Node类的定义如下：

//节点定义

function Node (data , left , right) {
  this.data = data;    // 数据
  this.left = left;    // 左节点
  this.right = right;   // 右节点
  this.show = show;    // 显示节点数据
}

function show(){
  return this.data;
}





Node对象既保存了数据，也保存了它的左节点和右节点的链接，其中 show 方法用来显示当前保存在节点中数据。


现在我们可以创建一个类，用来表示二叉查找数（BST），我们初始化类只包含一个成员，一个表示二叉查找树根节点的 Node 对象，初始化为 null ， 表示创建一个空节点。





//二叉查找树（BST）的类

function BST(){
  this.root = null;      // 根节点
  this.insert = insert;    // 插入节点
  this.preOrder = preOrder;  // 先序遍历
  this.inOrder = inOrder;   // 中序遍历
  this.postOrder = postOrder; // 后序遍历
  this.find = find;      // 查找节点
  this.getMin = getMin;    // 查找最小值
  this.getMax = getMax;    // 查找最大值
  this.remove = remove;    // 删除节点
}










现在，我们需要为我们的类添加方法。


首先就是 insert 方法，向树中添加一个新节点，我们一起来看看这个方法；


insert：向树中添加新节点


因为添加节点会涉及到插入位置的问题，必须将其放到正确的位置上，才能保证树的正确性，整个过程较为复杂，我们一起来梳理一下：


首先要添加新的节点，首先需要创建一个Node对象，将数据传入该对象。


其次要检查当前的BST树是否有根节点，如果没有，那么表示是一棵新数，该节点就为该树的根节点，那么插入这个过程就结束了；否则，就要继续进行下一步了。


如果待插入节点不是根节点，那么就必须对BST进行遍历，找到合适的位置。该过程类似遍历链表，用一个变量存储当前节点，一层一层遍历BST，算法如下：


    
  
  1. 设值当前节点为根节点
    2. 
  
  2. 如果待插入节点保存的数据小于当前节点，则新节点为原节点的左节点，反之，执行第4步
    3. 
  
  3. 如果当前节点的左节点为null，就将新节点放到这个位置，退出循环；反之，继续执行下一次循环
    4. 
  
  4. 设置新节点为原节点的右节点
    5. 
  
  5. 如果当前节点的右节点为null，就将新节点放到这个位置，退出循环；反之，继续执行下一次循环
    6. 



这样，就能保证每次添加的新节点能够放到正确的位置上，具体实现如下；





//插入新节点

function insert(data) {
  var n = new Node( data , null , null );
  if( this.root == null ){
    this.root = n;
  }else{
    var current = this.root;
    var parent;
    while( true ){
      parent = current;
      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的能力，上面我们也提到了是三种遍历方式。其中中序遍历是最容易实现的，我们需要升序的方法访问树中的所有节点，先访问左子树，在访问根节点，最后是右子树，我们采用递归来实现！


inOrder：中序遍历





 // 中序遍历
 
function inOrder (node) {
  if( !(node == null )){
    inOrder( node.left );
    console.debug( node.show() + ' ');
    inOrder( node.right );
  }
}










怎么样，了解了原理，实现起来还是蛮简单的~


我们用一段代码来测试一下我们所写的中序遍历：





var nums = new BST();
//插入数据
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);










上述插入数据后，会形成如下的二叉树


JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解 

BST


中序遍历结果如下：





//中序遍历
console.log("Inorder traversal: ");
inOrder(nums.root);

// Inorder traversal:
// 3 16 22 23 37 45 99










preOrder：先序遍历


有了中序遍历的基础，相信先序遍历的实现你已经想出来，怎么样？看看对吗？





//先序遍历

function preOrder( node ) {
  if( !(node == null )){
    console.log( node.show() + ' ');
    preOrder( node.left );
    preOrder( node.right );
  } 
}










怎么样，看起来是不是和中序遍历差不多，唯一的区别就是 if 语句中代码的执行顺序，中序遍历中 show 方法放在两个递归调用之间，先序遍历则放在递归调用之前。


先序遍历结果如下：





// 先序遍历

console.log("Preorder traversal: ");
preOrder(nums.root);

// Preorder traversal:
// 23 16 3 22 45 37 99