二叉排序树

Soarkey 发布于2019-08-23 14:14 / 513人阅读

摘要：节点的构造函数默认为其初始化都是。二叉排序树插入插入节点只要遵循一个原则就好大与就向中插入，小于就向插入。初始化数据树现在来试试实例化一个来看看效果。

JavaScript 数据结构篇之 BST 前言

有段时间没有写文章了，整个人感觉变得有点懒散了，大家可不要向我一样哦~
今天开始 seaconch 打算开始记录 JavaScript 数据结构的学习经历。
至此，开始。

课本：《学习JavaScript数据结构与算法 (第2版)》

术语：

BST (binary sort tree)

LST (left subtree)

RST (right subtree)

OUTLINE

特性

定义

插入

查找

最大

最小

移除

遍历

AVL

源码

特性

BST 有如下特性：

若 LST 不为空，则 LST 所有节点值都小于它的根节点值

若 RST 不为空，则 RST 所有节点值都大于它的根节点值

左右子树也都是 BST

没有重复键

定义

为了存储 BST，我们先定义一个 Node 类型，存储各个节点。

Node 节点的构造函数默认为其初始化 Subtree 都是 null。

/**
 * 节点
 */
class Node {

  constructor (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }

}

然后是 BST

BST 的类型我们只初始化了一个根节点 root。

/**
 * 二叉排序树
 */
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

}

插入

插入节点只要遵循一个原则就好：大与 node.key 就向 node.right 中插入，小于 node.key 就向 node.left 插入。

首先定义私有函数。

const insertNode = Symbol("insertNode");

  /**
   * 插入节点
   */
  insert(key) {

    let newNode = new Node(key);
    if (this.root === null) this.root = newNode;
    else this[insertNode](this.root, newNode);

  }

  /**
   * 插入节点
   * @param {当前节点} node 
   * @param {新节点} newNode 
   */
  [insertNode] (node, newNode) {

    if (newNode.key < node.key) {

      if (node.left === null) node.left = newNode;
      else this[insertNode](node.left, newNode);

    } else {

      if (node.right === null) node.right = newNode;
      else this[insertNode](node.right, newNode);

    }
  }

这里稍微的说明一下，之所以写成私有函数，无非就是为了不希望外部看到这些没必要的。

其实东西多了感觉也会乱糟糟的...

接下来为了查看一下效果，我们来写一个初始化 BST 的函数。

我们的目标是初始化一个这样的 BST。

/**
 * 初始化数据
 * @param {树} tree 
 */
function initialization(tree) {

  let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];

  treeKeys.forEach( key => tree.insert(key) )

}

现在来试试实例化一个 BST 来看看效果。

let tree = new BinarySearchTree();

initialization(tree);

console.log(tree.root);

打印效果如图

查找

由:

若 LST 不为空，则 LST 所有节点值都小于它的根节点值

若 RST 不为空，则 RST 所有节点值都大于它的根节点值

左右子树也都是 BST

因此我们可以相对快速的查找元素。

定义私有函数

const searchNode = Symbol("searchNode");

  /**
   * 是否存在目标 key
   */
  existKey(key) {
    return this[searchNode](this.root, key);
  }

  /**
   * 
   * @param {当前节点} node 
   * @param {key} key 
   */
  [searchNode] (node, key) {

    if (node === null) return false;
    
    if (key < node.key) return this[searchNode](node.left, key);
    
    else if (key > node.key) return this[searchNode](node.right, key);
    
    else return true;
    
  }

我们的思路是这样的：

如果要查找的 key值小于当前节点的 key值，则向 LST 继续查找;
如果要查找的 key值大于当前节点的 key值，则向 RST 继续查找;
如果要查找的 key值等于当前节点的 key值，则返回 true

运行效果如下：

最大值

由：

若 RST 不为空，则 RST 所有节点值都大于它的根节点值

左右子树也都是 BST

我们可以求得最大值

很明显是这样的

代码如下

定义私有函数

const maxNode = Symbol("maxNode");

  /**
   * 获取最大节点 key
   */
  max() {
    return this[maxNode](this.root);
  }

  /**
   * 获取最大节点 key
   * @param {节点} node 
   */
  [maxNode] (node) {

    if (node) {
    
      while (node && node.right !== null) {
      
        node = node.right;
      }
      return node.key;
    }
    return null;
  }

输出结果为：99

最小值

获取最小值的方法与最大值类似，只是方向变了一下

定义私有函数

const minNode = Symbol("minNode");

  /**
   * 获取最小节点 key
   */
  min() {
    return this[minNode](this.root);
  }

  /**
   * 获取最小节点 key
   * @param {节点} node 
   */
  [minNode] (node) {

    if (node) {
    
      while (node && node.left !== null) {
      
        node = node.left;
      }
      return node.key;
    }
    return null;
  }

运行结果自然是：5

移除

移除相对来说复杂一点，因为假如我们要移除的是一个父节点，那他们的子节点怎么办？

当然也是有相应的应对措施的。

对于没有 subtree 的 node 来说，只需要把他们修改为 null 即可

对于存在 subtree 的 node 来说，就要考虑所有情况分别处理

当 LST === null 时 => RST 上前来顶替待删除节点的位置

当 RST === null 时 => LST 上前来顶替待删除节点的位置

当 LST && RST 都不是 null 时，由 RST 中最小节点上前来顶起待删除节点的位置

图例说明：

1. LST 等于 null

2. RST 等于 null

3. LST 和 RST 都不等于 null

定义私有函数

const removeNode = Symbol("removeNode");
const findMinNode = Symbol("findMinNode");

  /**
   * 删除节点
   */
  remove(key) {
    this[removeNode](this.root, key);
  }

  /**
   * 删除节点，返回删除后的 tree
   * @param {当前节点} node 
   * @param {key} key 
   */
  [removeNode] (node, key) {

    if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;

    if (key < node.key) /** the key of currrent node is bigger than target key. */ {

      node.left = this[removeNode](node.left, key);
      return node;

    } else if (key > node.key) /** smaller */ {

      node.right = this[removeNode](node.right, key);
      return node;

    } else /** 相等 */ {

      if (node.left === null && node.right === null) {
        /**
         * 当前节点没有左右节点，可以放心删除
         */
        node = null;
        return node;
      }

      /**
       * 当前节点有一个节点，让子节点`顶`上来
       */
      if (node.left === null) {
        
        node = node.right;
        return node

      } else if (node.right === null) {

        node = node.left;
        return node;

      }

      /**
       * 来到这里代表当前节点有两个子节点
       */
      let aux = this[findMinNode](node.right); // 找到右节点的最小节点
      node.key = aux.key; // 把要删除的节点的 key 覆盖为右侧最小节点 key
      node.right = this[removeNode](node.right, aux.key); // 重构 right side tree (删除上面找到的 aux 节点)
      return node;
    }
  }

  /**
   * 返回目标节点分支下最小节点
   * @param {目标节点} node 
   */
  [findMinNode] (node) {

    while (node && node.left !== null) {
    
      node = node.left;
    }
    return node;
  }

好了，现在来一起运行一下，看一下效果吧

遍历

遍历 BST 一般有三种方式：

- 先序
- 中序
- 后序

seaconch 画了 3 张图帮助理解:

先序遍历：

中序遍历：

后序遍历：

这里我们只演示中序遍历的代码

中序遍历

所谓前序，中序，后序一般都是指具体操作的位置，在这里表示回调函数的位置

定义私有函数

const inOrderTraverseNode = Symbol("inOrderTraverseNode");

  /**
   * 中序遍历，标准名称为: `inOrderTraverse`
   */
  middleOrderTraverse(cb) {
    this[inOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {当前节点} node 
   * @param {回调} cb 
   */
  [inOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[inOrderTraverseNode](node.left, cb);
      cb(node.key); // 回调在中间就是中序
      this[inOrderTraverseNode](node.right, cb);
    }
  }

结果是按照顺序输出了各个节点的 key:

AVL

Adelson-Velskii-Landi(AVL) 自平衡树

BST 有一定的问题，比如当你添加了很多大于 root 的元素，而只添加了很少的小于 root 的元素，那么 BST 将严重失衡，最直观的一个说明就是，获取最大值的速度明显没有获取最小值的速度快。

AVL 树就是为了解决 BST 失衡的问题

AVL 在每次添加或删除元素的时候，尝试自平衡，使左右子树高度差 >= 1

(hr(右子树高度) - hl(左子树高度) in (-1, 0, 1))

源码

源码如下：

/**
 * 节点
 */
class Node {

  constructor (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

const insertNode = Symbol("insertNode");
const removeNode = Symbol("removeNode");
const findMinNode = Symbol("findMinNode");
const minNode = Symbol("minNode");
const maxNode = Symbol("maxNode");
const searchNode = Symbol("searchNode");
const inOrderTraverseNode = Symbol("inOrderTraverseNode");
const preOrderTraverseNode = Symbol("preOrderTraverseNode");
const postOrderTraverseNode = Symbol("postOrderTraverseNode");
/**
 * 二叉排序树
 */
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  /**
   * 插入节点
   */
  insert(key) {

    let newNode = new Node(key);
    if (this.root === null) this.root = newNode;
    else this[insertNode](this.root, newNode);

  }

  /**
   * 插入节点
   * @param {当前节点} node 
   * @param {新节点} newNode 
   */
  [insertNode] (node, newNode) {

    if (newNode.key < node.key) {

      if (node.left === null) node.left = newNode;
      else this[insertNode](node.left, newNode);

    } else {

      if (node.right === null) node.right = newNode;
      else this[insertNode](node.right, newNode);

    }
  }

  /**
   * 删除节点
   */
  remove(key) {
    this[removeNode](this.root, key);
  }

  /**
   * 删除节点，返回删除后的 tree
   * @param {当前节点} node 
   * @param {key} key 
   */
  [removeNode] (node, key) {

    if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;

    if (key < node.key) /** the key of currrent node is bigger than target key. */ {

      node.left = this[removeNode](node.left, key);
      return node;

    } else if (key > node.key) /** smaller */ {

      node.right = this[removeNode](node.right, key);
      return node;

    } else /** 相等 */ {

      if (node.left === null && node.right === null) {
        /**
         * 当前节点没有左右节点，可以放心删除
         */
        node = null;
        return node;
      }

      /**
       * 当前节点有一个节点，让子节点`顶`上来
       */
      if (node.left === null) {
        
        node = node.right;
        return node

      } else if (node.right === null) {

        node = node.left;
        return node;

      }

      /**
       * 来到这里代表当前节点有两个子节点
       */
      let aux = this[findMinNode](node.right); // 找到右节点的最小节点
      node.key = aux.key; // 把要删除的节点的 key 覆盖为右侧最小节点 key
      node.right = this[removeNode](node.right, aux.key); // 重构 right side tree (删除上面找到的 aux 节点)
      return node;
    }
  }

  /**
   * 返回目标节点分支下最小节点
   * @param {目标节点} node 
   */
  [findMinNode] (node) {

    while (node && node.left !== null) {

      node = node.left;
    }
    return node;
  }

  /**
   * 获取最小节点 key
   */
  min() {
    return this[minNode](this.root);
  }

  /**
   * 获取最小节点 key
   * @param {节点} node 
   */
  [minNode] (node) {

    if (node) {

      while (node && node.left !== null) {

        node = node.left;
      }
      return node.key;
    }
    return null;
  }

  /**
   * 获取最大节点 key
   */
  max() {
    return this[maxNode](this.root);
  }

  /**
   * 获取最大节点 key
   * @param {节点} node 
   */
  [maxNode] (node) {

    if (node) {

      while (node && node.right !== null) {

        node = node.right;
      }
      return node.key;
    }
    return null;
  }

  /**
   * 是否存在目标 key
   */
  existKey(key) {
    return this[searchNode](this.root, key);
  }

  /**
   * 
   * @param {当前节点} node 
   * @param {key} key 
   */
  [searchNode] (node, key) {

    if (node === null) return false;

    if (key < node.key) return this[searchNode](node.left, key);

    else if (key > node.key) return this[searchNode](node.right, key);

    else return true;

  }

  /**
   * 中序遍历，标准名称为: `inOrderTraverse`
   */
  middleOrderTraverse(cb) {
    this[inOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {当前节点} node 
   * @param {回调} cb 
   */
  [inOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[inOrderTraverseNode](node.left, cb);
      cb(node.key); // 回调在中间就是中序
      this[inOrderTraverseNode](node.right, cb);
    }
  }

  preOrderTraverse(cb) {
    this[preOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {*} node 
   * @param {*} cb 
   */
  [preOrderTraverseNode] (node, cb) {
    if (node !== null) {
      cb(node.key); // 回调在前
      this[preOrderTraverseNode](node.left, cb);
      this[preOrderTraverseNode](node.right, cb);
    }
  }

  postOrderTraverse(cb) {
    this[postOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {*} node 
   * @param {*} cb 
   */
  [postOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[postOrderTraverseNode](node.left, cb);
      this[postOrderTraverseNode](node.right, cb);
      cb(node.key); // 回调在后
    }
  }
}


/**
 * 初始化数据
 * @param {树} tree 
 */
function initialization(tree) {

  let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];

  treeKeys.forEach( key => tree.insert(key) )

}

let tree = new BinarySearchTree();

initialization(tree);

// tree.preOrderTraverse(v => console.log(v));
tree.middleOrderTraverse(v => console.log(v));
// tree.postOrderTraverse(v => console.log(v));

// console.log("the min node.key is: ", tree.min());
// console.log("the max node.key is: ", tree.max());

// let tempKey = 49;
// console.log("the key of [", tempKey, "]", tree.existKey(tempKey) ? "real" : "not", "exist.");

// tree.remove(49)
// console.log("remove key [", tempKey, "]");

// console.log("the key of [", tempKey, "]", tree.existKey(tempKey) ? "real" : "not", "exist.");

continue...

专线服务私有云二叉树排序树规则二叉排序树删除二叉排序树c语言二叉查找树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100324.html

二叉树遍历

摘要：前言本篇文章是在二叉排序树的基础上进行遍历查找与删除结点。接下来我们根据构造的这颗二叉树进行相应遍历查找与删除操作。遍历二叉树二叉树的遍历分为深度优先遍历和广度优先遍历。中序遍历二叉排序树，得到的数组是有序的且是升序的。前言本篇文章是在二叉排序树的基础上进行遍历、查找、与删除结点。那么首先来看一下什么是二叉排序树？二叉排序树定义二叉排序树，又称二叉查找树、二叉搜索树。若...

aboutU 2019-08-26 13:54 评论0 收藏0
JS实现二叉排序树

摘要：实现二叉排序树实现二叉排序树初始化二叉树只接受一个数组作为参数根节点接受传入的参数数组初始化每个树节点当前节点的值左子树右子树构建二叉树请选择一个数组参数插入节点当前需要插入的节点根节点不存在值时插入节点到根节点当前节点的小于父节点时当 JS实现二叉排序树 JS实现二叉排序树 1. 初始化二叉树 function BinaryTree (arr) { ...

sherlock221 2019-08-21 17:35 评论0 收藏0
JavaScript 数据结构与算法之美 - 非线性表中的树、堆是干嘛用的？其数据结构是怎样的？

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。非线性表中的树堆是干嘛用的其数据结构是怎样的希望大家带着这两个问题阅读下文。其中，前中后序，表示的是节点与它的左右子树节点遍历访问的先后顺序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想学好前端，先练好内功，内功不行，...

singerye 2019-08-26 10:09 评论0 收藏0
堆排序就这么简单

摘要：一堆排序介绍来源百度百科堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法，它是选择排序的一种。一、堆排序介绍来源百度百科：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。前面我已经有二叉树入门的文章了，当时讲解的是二叉查找树，那上面所说的完全二...

NickZhou 2019-08-19 10:43 评论0 收藏0
用JS实现数据结构----排序二叉树

摘要：代码实现创建一个排序二叉树节点类根节点插入节点以上便是创建排序二叉树的实现方式重点在于插入节点的具体实现，即注释的代码片段。排序二叉树 showImg(https://segmentfault.com/img/bVbfdbp?w=1047&h=472); 如上图为典型的排序二叉树，左孩子的值比节点的值小，右孩子的值比节点的值大，关于具体的树的定义及二叉树的定义可以百度或查阅相关资料。...

ispring 2019-08-23 11:00 评论0 收藏0