让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:)
和树相关的概念:
1.子树:由节点和他的后代构成,如上图标示处。
2.深度:节点的深度取决于它祖节点数量,比如节点5有2个祖节点,他的深度为2。
3.高度:树的高度取决于所有节点深度的最大值。
二叉树和二叉搜索树介绍:
二叉树中的节点最多只能有2个子节点,一个是左侧子节点,一个是右侧子节点,这样定义的好处是有利于我们写出更高效的插入,查找,删除节点的算法。
二叉搜索树是二叉树的一种,但是它只允许你在左侧子节点存储比父节点小的值,但在右侧节点存储比父节点大的值。接下来我们将按照这个思路去实现一个二叉搜索树。
1. 创建BinarySearchTree类
这里我们将使用构造函数去创建一个类:
我们将使用和链表类似的指针方式去表示节点之间的关系,如果不了解链表,请看我后序的文章《如何实现单向链表和双向链表》。
2.插入一个键
向树中插入一个新的节点主要有以下三部分:1.创建新节点的Node类实例 --> 2.判断插入操作是否为根节点,是根节点就将其指向根节点 --> 3.将节点加入非根节点的其他位置。
insertNode的具体实现如下:
这里我们用到递归,接下来要实现的search,del等都会大量使用递归,所以说不了解的可以先自行学习了解。我们创建一个二叉树实例,来插入一个键:
插入的结构会按照二叉搜索树的规则去插入,结构类似于上文的第一个树图。
树的遍历
访问树的所有节点有三种遍历方式:中序,先序和后序。
中序遍历:以从最小到最大的顺序访问所有节点
先序遍历:以优先于后代节点的顺序访问每个节点
后序遍历:先访问节点的后代节点再访问节点本身
根据以上的介绍,我们可以有以下的实现代码。
中序排序
使用中序遍历可以实现对树进行从小到大排序的功能。
先序排序
使用先序排序可以实现结构化输出的功能。
后序排序
// 后续遍历 --- 先访问后代节点,再访问节点本身
this.postOrderTraverse = function(cb) {
postOrderTraverseNode(root, cb);
}
// 后续遍历辅助方法
function postOrderTraverseNode(node, cb) {
if(node !== null){
postOrderTraverseNode(node.left, cb);
postOrderTraverseNode(node.right, cb);
cb(node.key);
}
}
后序遍历可以用于计算有层级关系的所有元素的大小。
搜索树中的值
在树中有三种经常执行的搜索类型:最大值,最小值,特定的值。
最小值
最小值通过定义可以知道即是左侧树的最底端的节点,具体实现代码如下:
相似的,实现最大值的方法如下:
2.搜索一个特定的值
移除一个节点
删除节点需要考虑的情况比较多,这里我们会使用和min类似的实现去写一个发现最小节点的函数,当要删除的节点有两个子节点时,我们要将当前要删除的节点替换为子节点中最大的一个节点的值,然后将这个子节点删除。
至此,一个二叉搜索树已经实现,但是还存在一个问题,如果树的一遍非常深,将会存在一定的性能问题,为了解决这个问题,我们可以利用AVL树,一种自平衡二叉树,也就是说任何一个节点的左右两侧子树的高度之差最多为1。
如果想学习更多js算法和数据结构,可以长按关注哦~
更多推荐
欢迎关注下方公众号,获取更多前端知识精粹和学习社群:
在公众号点击进群,可以加入vue学习小组,一起学习前端技术;
回复 学习路径,将获取笔者多年从业经验的前端学习路径的思维导图
趣谈前端
Vue、React、小程序、Node
前端 算法|性能|架构|安全