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

天衡 2019-08-23 13:20:07
原文地址:https://segmentfault.com/a/1190000020132804

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

树的相关术语

图片描述

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

二叉树和二叉搜索树

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

创建BinarySearchTree

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
};
class Node {
  constructor(key) {
    this.key = key;
    this.left = undefined;
    this.right = undefined;
  };
//下面我们会声明BinarySearchTree类的基本骨架
class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.root = undefined;
  }

向二叉搜索树插入一个键

insert(key) {
    // special case: first key
    if (this.root == null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left == null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else if (node.right == null) {
      node.right = new Node(key);
    } else {
      this.insertNode(node.right, key);
    }
  }

树的遍历

中序遍历

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

//inOrderTraverse接收回调函数作为参数
inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

  inOrderTraverseNode(node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }

先序遍历

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

preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

  preOrderTraverseNode(node, callback) {
    if (node != null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }

后序遍历

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

postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }

搜索树中的值

搜索最小值

min() {
    return this.minNode(this.root);
  }

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

搜索最大值

max() {
    return this.maxNode(this.root);
  }

  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }

搜索特定的值

search(key) {
    return this.searchNode(this.root, key);
  }

  searchNode(node, key) {
    if (node == null) {
      return false;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);
    } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    }
    return true;
  }

移除节点

removeNode(node, key) {
    if (node == null) {
      return undefined;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key);
      return node;
    } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key);
      return node;
    }
    // key is equal to node.item
    // handle 3 special conditions
    // 1 - a leaf node
    // 2 - a node with only 1 child
    // 3 - a node with 2 children
    // case 1 移除一个叶节点
    if (node.left == null && node.right == null) {
      node = undefined;
      return node;
    }
    // case 2 移除有一个左侧或者右侧子节点的节点
    if (node.left == null) {
      node = node.right;
      return node;
    } if (node.right == null) {
      node = node.left;
      return node;
    }
    // case 3    移除有两个子节点的节点
    const aux = this.minNode(node.right);
    node.key = aux.key;
    node.right = this.removeNode(node.right, aux.key);
    return node;
  }
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。