数据结构与算法对的javaScript描述-二叉搜索树

forrest23 发布于2019-08-21 18:24 / 1409人阅读

摘要：定义树以及相关概念二叉搜索树的定义首先是二叉树最多有两个节点，分别是左右节点子节点的位置是确定的，变现为左子节点的值小于其父节点右子节点的值大于其父节点在中的描述描述的完整代码传送门可视化传送门节点类树是由节点组成的，要实现树那么先要实现节

定义 树以及相关概念

二叉搜索树的定义

首先是二叉树

最多有两个节点，分别是左右节点

子节点的位置是确定的，变现为

左子节点的值小于其父节点

右子节点的值大于其父节点

BST在JS中的描述

JS描述的完整代码传送门
可视化BST传送门

节点类 Node

树是由节点组成的，要实现树那么先要实现节点

节点的要素

data:每个节点都需要有一个数值

left:左子节点，在没有左子节点的时候指向空对象null

right: 右子节点，在没有右子节点的时候指向空对象null

count: 计数值，累计插入的次数，这个是非必须的，作为一个要素是为了后续处理插入重复值的问题

show: 显示方法，展示该节点的值（和插入次数），在这里返回一个包含值（和插入次数）的对象

js的描述

class Node {
  constructor (data,
               count = 1,
               left = null,
               right = null)
  {
    // 数值
    this.data = data
    // 出现次数
    this.count = count
    // 左右节点指向
    this.left = left
    this.right = right
  }
  show () {
    return {
      data: this.data,
      count: this.count
    }
  }
}

BST 二叉搜索树类 属性

目前我们只需要一个根节点的属性，因此一个基本的BST可以描述为:

class BST {
  constructor () {
    // 初始化跟节点为null
    this.root = null
  }
}

插入方法

我们有了一个基本的BST,这时候我们可以new一个 bst，那么我们怎么插入数据呢？这时候我们需要一个insert方法，这个方法有以下的条件：

插入的是节点，也就是上述的类Node的一个实例

如果没有根节点，bst的根节点指向该节点

如果有根节点则向下遍历，找到合适的位置插入该节点，遍历规则如下图：

带有插入方法的BSTjs的描述如下

class BST {
  constructor () {
    // 初始化跟节点为null
    this.root = null
  }
  /**
   * 插入数据
   * @param data
   */
  insert (data) {
    let n = new Node(data, 1)
    if (this.root === null) {
      // 没有根节点，新的树把待插入的值作为根节点
      this.root = n
    } else {
      // 有根节点，遍历树直到找到合适的位置
      let current = this.root
      while (true) {
        if (data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else if (data === current.data) {
          current.count += 1
          break
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }
  }
}

插入一组测试数据测试

let testData = [
  43,
  34,
  67,
  23,
  34,
  45,
  2,
  78,
  34
]

let bst = new BST()
console.log(JSON.stringify(bst))

for (let data of testData) {
  bst.insert(data)
}
console.log(JSON.stringify(bst))

插入数据前：

{"root":null}

插入数据后

{
    "root": {
        "data": 43,
        "count": 1,
        "left": {
            "data": 34,
            "count": 3,
            "left": {
                "data": 23,
                "count": 1,
                "left": {
                    "data": 2,
                    "count": 1,
                    "left": null,
                    "right": null
                },
                "right": {
                    "data": 28,
                    "count": 1,
                    "left": null,
                    "right": null
                }
            },
            "right": null
        },
        "right": {
            "data": 67,
            "count": 1,
            "left": {
                "data": 45,
                "count": 1,
                "left": null,
                "right": null
            },
            "right": {
                "data": 78,
                "count": 1,
                "left": null,
                "right": null
            }
        }
    }
}

插入数据之后我们是通过nodejs的logger来查看bst，事实上，我们还需要其他的遍历方法来查看bst

BST的遍历

遍历二叉树通常有三种遍历方法，分别是中序、先序和后序，他们的遍历路径不一样

中序遍历

中序遍历应该是最常用的一种遍历方法

js中的描述

/**
   * 中序遍历
   * @param node
   */
  inOrder (node) {
    if (node !== null) {
      this.inOrder(node.left)
      console.log(`data:${node.data},count:${node.count}`)
      this.inOrder(node.right)
    }
  }

上述例子中的输出结果

中序
data:2,count:1
data:23,count:1
data:28,count:1
data:34,count:3
data:43,count:1
data:45,count:1
data:67,count:1
data:78,count:1

路径图

先序遍历

js中的描述

  /**
   * 先序遍历
   * @param node
   */
  preOrder (node) {
    if (node !== null) {
      console.log(`data:${node.data},count:${node.count}`)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }

上述例子中的输出结果

先序
data:43,count:1
data:34,count:3
data:23,count:1
data:2,count:1
data:28,count:1
data:67,count:1
data:45,count:1
data:78,count:1

路径图

后序遍历

js中的描述

  /**
   * 后序遍历
   * @param node
   */
  postOrder (node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(`data:${node.data},count:${node.count}`)
    }
  }

上述例子中的输出结果

后序
data:2,count:1
data:28,count:1
data:23,count:1
data:34,count:3
data:45,count:1
data:78,count:1
data:67,count:1
data:43,count:1

路径图

查找

在二叉搜索树中查找数据非常简单

最大值与最小值

最小值为树中的最左边的叶子节点得到值，最大值为最右边子节点的值

  /**
   * 查找最小值
   * @returns {CanvasPixelArray|string|Object[]|*}
   */
  getMin (node) {
    let current = node || this.root
    while (current.left !== null) {
      current = current.left
    }
    return current
  }
  
  /**
   * 查找最大值
   * @returns {CanvasPixelArray|string|Object[]|*}
   */
  getMax (node) {
    let current = node || this.root
    while (current.right !== null) {
      current = current.right
    }
    return current
  }

查找指定数据

根据数据的大小判断向左向右查找使得查找非常有效率

  /**
   * 查找数据
   * @param data
   * @returns {*}
   */
  find (data) {
    let current = this.root,
      result = null
    while (current !== null) {
      if (data === current.data) {
        result = current
        break
      } else if (data < current.data) {
        current = current.left
      } else {
        current = current.right
      }
    }
    return result
  }

bst.getMax().data // 78
bst.getMax().count // 1
bst.getMin().data // 2
bst.getMin().count // 1

删除数据

删除数据其实是操作二叉搜索树中最麻烦的一部分

我的思路如下：

待删除节点没有子节点：

父节点链向该节点的链接指向null

待删除节点只有左节点或者右节点

父节点链向他的链接指向他的子节点

待删除节点既有左节点又有右节点

用他的右子树的最小节点取代（值和计数替代）待删除节点

在他的右子树中删除右子树中的最小节点

基于此，JS中的描述为

  /**
   * 删除数据
   * @param data
   */
  remove ( data ) {
    this.root = this.removeDataFromNode(this.root, data)
  }
  
  /**
   * 从指定节点中删除数据
   * @param node
   * @param data
   * @returns {*}
   */
  removeDataFromNode (node, data) {
    if (node !== null) {
      if (data === node.data) {
        if (node.left === null && node.right === null) {
        //  没有子节点
          return null
        }
        if (node.right === null) {
        //  只有左节点
          return node.left
        }
        if (node.left === null) {
        //  只有右节点
          return node.right
        }
        // 有做节点和右节点
        // 取右节点的最小值
        let tempNode = this.getMin(node.right)
        node.data = tempNode.data
        node.count = tempNode.count
        node.right = this.removeDataFromNode(node.right, tempNode.data)
        return node
      } else if (data < node.data) {
        node.left = this.removeDataFromNode(node.left, data)
        return node
      } else {
        node.right = this.removeDataFromNode(node.right, data)
        return node
      }
    } else {
      return null
    }
  }

云服务器 GPU云服务器二叉树算法最优二叉树算法图描述的数据结构与算法 c语言二叉树输入数据

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

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

Python数据结构——二叉搜索树的实现（上）

摘要：图展示了二叉搜索树的这一特性，显示的键没有关联任何的值。因为我们必须能够创建和使用一个空的二叉搜索树，所以我们将使用两个类来实现，第一个类我们称之为，第二个类我们称之为。图说明了将新节点插入到一个二叉搜索树的过程。二叉搜索树我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT（抽象数据类型）MAP的。我们讨论两种ADT MAP的实现方式，基于列表的...

AbnerMing 2019-07-31 11:41 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

zsirfs 2019-08-23 15:33 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0
数据结构与算法JavaScript （不定时更新）

摘要：每个列表中的数据项称为元素。栈被称为一种后入先出，的数据结构。散列使用的数据结构叫做散列表。不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。因此二叉搜索树需要平衡，即左右子树高度要相近。楼楼非计算机专业，但是对计算机也还算喜欢。个人理解若有偏差，欢迎各位批评指正！对于数据结构和算法一直是我的薄弱环节，相信大多数前端工程师可能多少会有些这方面的弱点，加上数据结构和算法本...

levius 2019-08-26 11:40 评论0 收藏0