数据结构之树

树

树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱，或是公司的组织架构图

树的相关术语

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点

树

根据上图:

位于树顶部的节点叫做根节点(11)
树中的每个元素都叫作节点，节点分为内部节点和外部节点
- 至少有一个子节点的节点称为内部节点（7、5、9、15、13 和 20 是内部节点）
- 没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18 和 25 是叶节点）
一个节点可以有祖先和后代
- 一个节点（除了根节点）的祖先包括父节点、祖父节点、曾祖父节点等, 节点 5 的祖先有节点 7 和节点 11，
- 一个节点的后代包括子节点、孙子节点、曾孙节点等, 节点 5 后代有节点 3 和节点 6
树的另一个术语是子树
- 子树由节点和它的后代构成。例如，节点 13、12 和 14 构成了上图中树的一棵子树
节点的一个属性是深度
- 节点的深度取决于它的祖先节点的数量。比如，节点 3 有 3 个祖先节点（5、7 和 11），它的深度为 3
树的高度取决于所有节点深度的最大值
- 一棵树也可以被分解成层级。根节点在第 0 层，它的子节点在第 1 层，以此类推。上图中的树的高度为 3（最大高度已在图中表示——第 3 层）

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点, 二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。上一节的图中就展现了一棵二叉搜索树

创建二叉搜索树(BinarySearchTree)类

二叉搜索树数据结构组织方式

上图展现了二叉搜索树数据结构的组织方式, 先来创建 Node 类来表示二叉搜索树中的每个节点

和链表一样, 我们通过指针(引用)来表示节点之间的关系, 树也是用两个指针, 但一个指向左侧子节点, 另一个指向右侧子节点, 不同于在之前的章节中将节点本身称作节点或项，我们将会称其为键

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

声明一个 BinarySearchTree 类的基本结构

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }
}

实现一些方法
- insert(key):想树中插入一个新的键
- search(key):向树中查找一个键, 如果节点存在, 返回 true, 否则返回 false
- inOrderTraverse():通过中序遍历方式遍历所有节点
- preOrderTraverse():通过先序遍历方式遍历所有节点
- postOrderTravsese():通过后序遍历方式遍历所有节点
- min():返回树中的最小值/键
- max():返回树中的最大的值/键
- remove(key):从树中移除某个键
向二叉搜索树插入一个值

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  //
  // 如果树非空，需要找到插入新节点的位置。因此，在调用 insertNode 方法时要通过参数传入树的根节点和要插入的节点
  insertNode(node, key) {
    // 如果新节点的键小于当前节点的键
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      // 检查当前节点的左侧子节点, 如果它没有左侧子节点
      if (node.left == null) {
        // 在那里插入新的节点
        node.left = new Node(key);

        // 有左侧子节点，需要通过递归调用 insertNode方法
      } else {
        this.insertNode(node.left, key);
      }
    } else {
      // 节点的键比当前节点的键大，同时当前节点没有右侧子节点
      if (node.right == null) {
        node.right = new Node(key);

        // 有右侧子节点，同样需要递归调用 insertNode 方法
      } else {
        this.insertNode(node.right, key);
      }
    }
  }

  insert(key) {
    // 尝试插入的树节点是否为第一个节点
    if (this.root == null) {
      // 创建一个 Node 类的实例并将它赋值给 root 属性来将 root 指向这个新节点, 左指针和右指针的值会由构造函数自动设置为 null
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }
}

tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);

insert

树的遍历之中序遍历

遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程, 访问树的所有节点有三种方式：中序、先序和后序

中序遍历

中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  /**
   * 中序遍历
   * @param {接收一个回调函数作为参数} callback
   */
  inOrderTraverse(callback) {
    // 定义我们对遍历到的每个节点进行的操作
    this.inOrderTraverseNode(this.root, callback);
  }

  // 辅助方法，来接收一个节点和对应的回调函数作为参数
  inOrderTraverseNode(node, callback) {
    // 首先要检查以参数形式传入的节点是否为 null, 停止递归继续执行的判断条件
    if (node != null) {
      // 递归调用相同的函数来访问左侧子节点, 再访问右侧子节点
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
}

const printNode = (value) => console.log(value); // {6}
tree.inOrderTraverse(printNode); // {7}

中序遍历

树的遍历之先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的, 先序遍历的一种应用是打印一个结构化的文档

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  preOrderTraveser(callback) {
    this.preOrderTraveserNode(this.root, callback);
  }

  preOrderTraveserNode(node, callback) {
    if (node != null) {
      // 先序遍历会先访问节点本身
      callback(node.key);
      // 再访问左侧子节点
      this.preOrderTraveserNode(node.left, callback);
      // 在访问右侧子节点
      this.preOrderTraveserNode(node.right, callback);
    }
  }
}

// 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

先序遍历路径

后序遍历

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

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  // 后序遍历
  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);
    }
  }
}

// 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

后序

搜索树中的值

搜索最大值和最小值

看树中最大值和最小值

// 上图树的最左端是最小值, 最右端是最大值

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  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 方法

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  // 声明 search 方法。和 BST 中声明的其他方法的模式相同，我们将会使用一个辅助方法
  search(key) {
    return this.searchNode(this.root, key);
  }

  // searchNode 方法可以用来寻找一棵树或其任意子树中的一个特定的值
  searchNode(node, key) {
    // 验证作为参数传入的 node 是否合法
    if (node == null) return false;
    // 要找的键比当前的节点小, 在左侧的子树上搜索
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);

      // 要找的键比当前的节点大, 从右侧子节点开始继续搜索
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }
}
// 执行该方法来查找 1 这个键

/**
 * 调用 searchNode 方法，传入根节点作为参数, node[root[11]]不为 null
 * key[1] < node[11]为真, 再次调用 searchNode 方法，传入 node[7], key[1]作为参数
 * node[7]不为 null，因此继续执行行
 * key[1] < node[7]为真, 再次调用 searchNode 方法，传入 node[5], key[1]作为参数
 * node[5]不为 null，因此继续执行行
 * key[1] < node[5]为真, 入 node[3], key[1]作为参数
 * /

移除一个节点

为 BST 实现的下一个、也是最后一个方法是 remove 方法

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    // 将声明一个变量以控制此数据结构的第一个节点。在树中，它不再是 head，而是 root
    this.root = null;
  }

  //
  // 如果树非空，需要找到插入新节点的位置。因此，在调用 insertNode 方法时要通过参数传入树的根节点和要插入的节点
  insertNode(node, key) {
    // 如果新节点的键小于当前节点的键
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      // 检查当前节点的左侧子节点, 如果它没有左侧子节点
      if (node.left == null) {
        // 在那里插入新的节点
        node.left = new Node(key);

        // 有左侧子节点，需要通过递归调用 insertNode方法
      } else {
        this.insertNode(node.left, key);
      }
    } else {
      // 节点的键比当前节点的键大，同时当前节点没有右侧子节点
      if (node.right == null) {
        node.right = new Node(key);

        // 有右侧子节点，同样需要递归调用 insertNode 方法
      } else {
        this.insertNode(node.right, key);
      }
    }
  }

  insert(key) {
    // 尝试插入的树节点是否为第一个节点
    if (this.root == null) {
      // 创建一个 Node 类的实例并将它赋值给 root 属性来将 root 指向这个新节点, 左指针和右指针的值会由构造函数自动设置为 null
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  /**
   * 中序遍历
   * @param {接收一个回调函数作为参数} callback
   */
  inOrderTraverse(callback) {
    // 定义我们对遍历到的每个节点进行的操作
    this.inOrderTraverseNode(this.root, callback);
  }

  // 辅助方法，来接收一个节点和对应的回调函数作为参数
  inOrderTraverseNode(node, callback) {
    // 首先要检查以参数形式传入的节点是否为 null, 停止递归继续执行的判断条件
    if (node != null) {
      // 递归调用相同的函数来访问左侧子节点, 再访问右侧子节点
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }

  // 先序遍历
  preOrderTraveser(callback) {
    this.preOrderTraveserNode(this.root, callback);
  }

  preOrderTraveserNode(node, callback) {
    if (node != null) {
      callback(node.key);
      this.preOrderTraveserNode(node.left, callback);
      this.preOrderTraveserNode(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 方法。和 BST 中声明的其他方法的模式相同，我们将会使用一个辅助方法
  search(key) {
    return this.searchNode(this.root, key);
  }

  // searchNode 方法可以用来寻找一棵树或其任意子树中的一个特定的值
  searchNode(node, key) {
    // 验证作为参数传入的 node 是否合法
    if (node == null) return false;
    // 要找的键比当前的节点小, 在左侧的子树上搜索
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);

      // 要找的键比当前的节点大, 从右侧子节点开始继续搜索
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }

  remove(key) {
    // 传入 root 和要移除的键作为参数
    this.root = this.removeNode(this.root, key);
  }

  removeNode(node, key) {
    // 正在检测的节点为 null，那么说明键不存在于树中，所以返回 null
    if (node == null) return null;

    // 要找的键比当前节点的值小, 沿着树的左边找到下一个节点
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key);
      return node;

      // 要找的键比当前节点的值大, 沿着树的右边找到下一个节点
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      // 找到了要找的键（键和 node.key 相等），就需要处理三种不同的情况

      // 第一种情况是该节点是一个没有左侧或右侧子节点的叶节点
      if (node.left == null && node.right == null) {
        // 是给这个节点赋予 null 值来移除它
        node = null;
        // 需要处理引用（指针）。在这里，这个节点没有任何子节点，但是它有一个父节点，需要通过返回 null 来将对应的父节点指针赋予 null 值
        return node;
      }

      // 第二种情况移除有一个左侧子节点或右侧子节点的节点, 需要跳过这个节点，直接将父节点指向它的指针指向子节点
      // 这个节点没有左侧子节点, 也就是说它有一个右侧子节点, 把对它的引用改为对它右侧子节点的引用, 返回更新后的节点
      if (node.left == null) {
        node = node.right;
        return node;
      } else if (node.right == null) {
        node = node.left;
        return node;
      }

      // 第三种情况, 要移除的节点有两个子节点——左侧子节点和右侧子节点
      // 当找到了要移除的节点后，需要找到它右边子树中最小的节点
      const aux = this.minNode(node.right);
      // 用它右侧子树中最小节点的键去更新这个节点的值, 通过这一步，我们改变了这个节点的键，也就是说它被移除了
      node.key = aux.key;
      // 这样在树中就有两个拥有相同键的节点了，这是不行的。要继续把右侧子树中的最小节点移除，毕竟它已经被移至要移除的节点的位置了
      node.right = this.removeNode(node.right, aux.key);
      // 向它的父节点返回更新后节点的引用
      return node;
    }
  }
}

移除一个叶节点

只有一个子节点

移除两个节点

自平衡树

BST 存在一个问题：取决于你添加的节点数，树的一条边可能会非常深；也就是说，树的一条分支会有很多层，而其他的分支却只有几层, 如下图

BST

在需要在某条边上添加、移除和搜索某个节点时引起一些性能问题。为了解决这个问题，有一种树叫作 Adelson-Velskii-Landi 树（AVL 树）AVL 是一种自平衡二叉搜索树, 意思是任何一个节点左右两侧子树的高度之差最多为 1

后续继续更新, 先熟悉一下

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,126评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,254评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,445评论 0赞 341
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,185评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,178评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,970评论 1赞 284
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,276评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,927评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,400评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,883评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,997评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,646评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,213评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,204评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,423评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,423评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,722评论 2赞 345

数据结构之树

树

搜索树中的值

自平衡树

推荐阅读更多精彩内容