跳到主要内容位置

概念

树是一种递归的数据结构,与链表类似:

  • 一棵树有且只有一个根节点。
  • 每个节点有 0 到多个子节点。
  • 每个子节点还有 0 到多个子节点。
  • 以此类推。
  • 每个节点还会保存节点的值

相邻的节点称为邻居节点,没有子节点的节点称为叶子节点,树的层数称为树的高度。 ​

除根节点外,子节点以及它后续节点形成的树称为子树。

应用

树是应用最为广泛的数据结构之一,例如:

  • HTML DOM / Virtual DOM 结构。
  • 索引。
  • 文件系统。
  • 自动补全功能。

等等等等。

分类

树的分类有多种,根据子节点的数量不同,可分为二叉树、三叉树或多叉树。最常见的是二叉树,每个节点最多有两个子节点。多叉树常见的有字典树。 对于二叉树,根据节点的排列和数量,也分为下面几种常见的类型:

  • 完全二叉树(Completed Binary Trees):每一层的节点都拥有 2 个子节点,最后一层除外,最后一层空缺的节点必须在右边,左边必须填满。
  • 满二叉树(Full Bnary Trees):每个节点要么有 2 个子节点,要么没有子节点,不能只有 1 个子节点。
  • 完美二叉树(Perfect Binary Trees):所有的节点都有两个子节点,最后一层都是叶子节点。
  • 平衡二叉树(Balanced Binary Trees):平衡二叉树的定义并不是很严格,不同的场景有不同的定义,对于一棵二叉树,如果大体上左右两棵子树看起来比较平衡,它就是平衡二叉树,有的定义是左右子树的每个节点的高度差都不大于 1。
  • 二叉搜索树(Binary Search Trees):左子节点的值 <= 该节点值 < 右子节点的值,并且左节点和它后续节点的值都小于等于该节点的值,右节点和它后续的值都大于该节点的值,这样形成的树方便进行搜索和排序,所以叫作二叉搜索树。对于和节点值相同的子节点应该放左边还是右边,不同的实现有不同的规定。
  • 自平衡二叉搜索树(Self-Balancing Binary Search Trees):这种树在平衡二叉树和搜索二叉树的基础上,会根据节点的插入和删除,自动保持平衡,常见的有红黑树和 AVL 树,不过这两种树的实现比较复杂。

JavaScript 实现

由于二叉树是最常用的数据结构,并且比较简单,我们来看一下它的 JavaScript 实现。另外对于树的遍历、查找、添加节点、删除节点等涉及的操作比较复杂,我们在后面的视频中再逐一学习,这里主要看一下二叉树的节点结构。 二叉树的代码与链表类似,我们使用一个 TreeNode class 来代表树的节点:

  • 节点有一个 value 属性,保存树的值。
  • 然后有 left 属性,保存左子节点的引用。
  • 最后有 right 属性,保存右子节点的引用。
  • 子节点的类型都是 TreeNode,这是一个递归的类型。
  • 在构造函数中赋值的时候,如果没给其中的某些属性传值,那么就给它们设置默认值,value 默认为 0,left 和 right 子节点默认为 null。
class TreeNode {
constructor(value, left, right) {
this.value = (value ? value : 0;
this.left = (left ? left : null);
this.right = (right ? right : null);
}
}

之后可以定义一个 BinaryTree class,里边保存一个根节点的值,因为树也是递归结构,所以通过根节点可以找到所有子节点,类的剩余部分可以定义和二叉树有关的操作:

class BinaryTree {
constructor(root) {
this.root = root;
}
// 其它方法
}

小结

好了,这个就是树的定义和分类,以及 JavaScript 的表示方法,你学会了吗?如果有帮助请三连,想学更多有用的前端开发知识,请关注峰华前端工程师,感谢观看!