资讯专栏INFORMATION COLUMN

JavaScript数据结构与算法(九)二叉树和二叉搜索树

zhaofeihao / 3368人阅读

摘要:二叉树和二叉搜索树二叉树的节点最多只能有两个节点,而二叉搜索树只允许在左侧的节点处存储比父节点小的值,在右侧节点存储比父节点大的值。接收回调函数作为参数先序遍历先序遍历是以优先于后代节点的顺序访问没和节点的。

树是一种非顺序数据结构,对于存储需要快速查找的数据非常有用。树是一种分层数据的抽象模型,现实生活中最常见的例子就是家谱,或者是公司的组织架构图。

树的相关术语

树中的每一个元素都是节点,节点分为内部节点和外部节点。其中:
至少有一个子节点的节点称为内部节点(例如图中节点7,5,9,15,13,20),没有子元素的节点为外部节点或叶节点(例如图中节点3,6,8,10,12,14,18,25)。
位于树顶部的节点叫做根节点,它没有父节点。
节点的一个属性是深度,节点的深度 取决于它的祖先节点的数量。树的高度取决于深度的最大值。同样一棵树也可以分为层级,根节点在第0层,它的子节点在第1层,以此类推。

二叉树和二叉搜索树

二叉树的节点最多只能有两个节点,而二叉搜索树只允许在左侧的节点处存储(比父节点)小的值,在右侧节点存储(比父节点)大的值。

创建BinarySearchTree

</>复制代码

  1. const Compare = {
  2. LESS_THAN: -1,
  3. BIGGER_THAN: 1,
  4. EQUALS: 0
  5. };
  6. function defaultCompare(a, b) {
  7. if (a === b) {
  8. return Compare.EQUALS;
  9. }
  10. return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
  11. };
  12. class Node {
  13. constructor(key) {
  14. this.key = key;
  15. this.left = undefined;
  16. this.right = undefined;
  17. };
  18. //下面我们会声明BinarySearchTree类的基本骨架
  19. class BinarySearchTree {
  20. constructor(compareFn = defaultCompare) {
  21. this.compareFn = compareFn;
  22. this.root = undefined;
  23. }
向二叉搜索树插入一个键

</>复制代码

  1. insert(key) {
  2. // special case: first key
  3. if (this.root == null) {
  4. this.root = new Node(key);
  5. } else {
  6. this.insertNode(this.root, key);
  7. }
  8. }
  9. insertNode(node, key) {
  10. if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  11. if (node.left == null) {
  12. node.left = new Node(key);
  13. } else {
  14. this.insertNode(node.left, key);
  15. }
  16. } else if (node.right == null) {
  17. node.right = new Node(key);
  18. } else {
  19. this.insertNode(node.right, key);
  20. }
  21. }
树的遍历 中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式,也就是从最小到最大的顺序访问所有节点。中序遍历的一种应用是对树进行排序操作。

</>复制代码

  1. //inOrderTraverse接收回调函数作为参数
  2. inOrderTraverse(callback) {
  3. this.inOrderTraverseNode(this.root, callback);
  4. }
  5. inOrderTraverseNode(node, callback) {
  6. if (node != null) {
  7. this.inOrderTraverseNode(node.left, callback);
  8. callback(node.key);
  9. this.inOrderTraverseNode(node.right, callback);
  10. }
  11. }
先序遍历

先序遍历是以优先于后代节点的顺序访问没和节点的。先序遍历的一种应用是打印一个结构化的文档、我们来看代码实现

</>复制代码

  1. preOrderTraverse(callback) {
  2. this.preOrderTraverseNode(this.root, callback);
  3. }
  4. preOrderTraverseNode(node, callback) {
  5. if (node != null) {
  6. callback(node.key);
  7. this.preOrderTraverseNode(node.left, callback);
  8. this.preOrderTraverseNode(node.right, callback);
  9. }
  10. }
后序遍历

后序遍历就是县访问节点的后代节点,在访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小

</>复制代码

  1. postOrderTraverse(callback) {
  2. this.postOrderTraverseNode(this.root, callback);
  3. }
  4. postOrderTraverseNode(node, callback) {
  5. if (node != null) {
  6. this.postOrderTraverseNode(node.left, callback);
  7. this.postOrderTraverseNode(node.right, callback);
  8. callback(node.key);
  9. }
  10. }
搜索树中的值 搜索最小值

</>复制代码

  1. min() {
  2. return this.minNode(this.root);
  3. }
  4. minNode(node) {
  5. let current = node;
  6. while (current != null && current.left != null) {
  7. current = current.left;
  8. }
  9. return current;
  10. }
搜索最大值

</>复制代码

  1. max() {
  2. return this.maxNode(this.root);
  3. }
  4. maxNode(node) {
  5. let current = node;
  6. while (current != null && current.right != null) {
  7. current = current.right;
  8. }
  9. return current;
  10. }
搜索特定的值

</>复制代码

  1. search(key) {
  2. return this.searchNode(this.root, key);
  3. }
  4. searchNode(node, key) {
  5. if (node == null) {
  6. return false;
  7. }
  8. if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  9. return this.searchNode(node.left, key);
  10. } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
  11. return this.searchNode(node.right, key);
  12. }
  13. return true;
  14. }
移除节点

</>复制代码

  1. removeNode(node, key) {
  2. if (node == null) {
  3. return undefined;
  4. }
  5. if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
  6. node.left = this.removeNode(node.left, key);
  7. return node;
  8. } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
  9. node.right = this.removeNode(node.right, key);
  10. return node;
  11. }
  12. // key is equal to node.item
  13. // handle 3 special conditions
  14. // 1 - a leaf node
  15. // 2 - a node with only 1 child
  16. // 3 - a node with 2 children
  17. // case 1 移除一个叶节点
  18. if (node.left == null && node.right == null) {
  19. node = undefined;
  20. return node;
  21. }
  22. // case 2 移除有一个左侧或者右侧子节点的节点
  23. if (node.left == null) {
  24. node = node.right;
  25. return node;
  26. } if (node.right == null) {
  27. node = node.left;
  28. return node;
  29. }
  30. // case 3 移除有两个子节点的节点
  31. const aux = this.minNode(node.right);
  32. node.key = aux.key;
  33. node.right = this.removeNode(node.right, aux.key);
  34. return node;
  35. }
  36. }

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

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

相关文章

  • 一篇文章学会二叉和二叉查找

    摘要:二叉树和二叉查找树一个父节点的两个子节点分别称为左节点和右节点。下图展示了一颗二叉树当考虑某种特殊的二叉树,比如二叉查找树时,确定子节点非常重要。实现二叉查找树定义对象。现在可以创建一个类来表示二叉查找树。因此二叉查找树也被叫做二叉排序树。 树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构,以分层的方式存储数据。 树被用来存储具有层级关系的数据,比如文件系统中的文件。 ...

    BaronZhang 评论0 收藏0
  • 每周一练 之 数据结构算法(Tree)

    摘要:假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。代码实现二叉树节点定义来源验证二叉搜索树解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 ...

    zhonghanwen 评论0 收藏0
  • 每周一练 之 数据结构算法(Tree)

    摘要:假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。代码实现二叉树节点定义来源验证二叉搜索树解析这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据结构与算法(LinkedList) 3...

    fizz 评论0 收藏0
  • 学习javascript数据结构(四)——

    摘要:原文博客地址学习数据结构四树知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人之所能,不能兼备,弃其所短,取其所长。通常子树被称作左子树和右子树。敬请期待数据结构篇最后一篇文章学习数据结构五图参考文章树数据结构二叉树 前言 总括: 本文讲解了数据结构中的[树]的概念,尽可能通俗易懂的解释树这种数据结构的概念,使用javascript实现了树,如有纰漏,欢迎批评指正。 ...

    Dean 评论0 收藏0

发表评论

0条评论

zhaofeihao

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<