图：园南小学

如果要系统的学习某个知识的话，我感觉选择相关知识的一本经典书籍来阅读是一个很好的选择。

因为书本：

• 系统性
• 具有较强的权威性（发现一个百万粉丝的计算机博主，习惯把树的高度定义为根节点到最远叶子的节点数，这样算出来的高度就总会比书本上的多一层，这样可能就会让人感到疑惑）

《数据结构》与《算法》是CS专业最为重要的两门课，特别是对于从事软件开发的同学，也是面试中作为基础知识的最重要的考查点。

这次重新学习数据结构与算法，我主要选了两本书籍作为指南 -《学习Javascript数据结构与算法》和《算法导论》，记得大学的时候，我们的数据结构课本是学校的自编教材，质量实在一般，我也就不太爱看:(。其中《学习Javascript数据结构与算法》主要是用Js代码将主要的数据结构以及操作实现了一遍，整体简洁干练，其中也不乏深度和广度，而且很多定义我都在维基百科或教科书上查询过，我认为是比较权威的，挺适合前端人员想学习数据结构的同学。《算法导论》则是很深入讲解算法理论知识的一本经典书籍，里面有大量的数学论证，数学不好的同学可能会看得很吃力，比如说我😫。我是配合b站的书籍作者Charles教授的MIT公开课来学习的，也没有太多的深入。不过如果你能完全搞懂，相信能超越90%程序员，。。

来自知乎的热门话题 - 为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？

图：树在数据结构中的“地位”

树都是用的链表的形式来组织，所以属于线性表中的链式存储结构，区别于用数组组织的顺序存储结构。而二叉树是最常见的一种树的类型。

以下是二叉树的定义

“二叉树中的节点最多只能有两个子节点，一个是左侧子节点，另一个是右侧子节点”

而二叉树中又有两种常见的分类 - Binary Search Tree（二叉搜索树）和 Adelson-Velskii-Landi Tree（自平衡二叉搜索树）。

BST:

BST是二叉树的一种，但是只允许在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值。

以下我们来详细的实现下BST，

BST的常见操作：

• 中序遍历（先依次访问左节点，再访问根节点，最后访问右节点，遍历完成后，根节点位于左子树节点与右子树节点中间。）
• 先序遍历（根节点位于左右子树节点之前，先访问父节点后访问左、右子节点）
• 后序遍历（根节点位于左右子树节点之后,先访问左、右子节点后访问父节点）
• 插入
• 删除某个键
• 搜索
• 返回最大/最小键

数据结构

怎么用JS定义Tree的数据结构？

1. 先定义Tree的每个节点，都包含 - 键（树中习惯叫键，不同于链表的值），左子树、右子树的引用。

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

树节点的实现跟双向链表的实现很像，只是把 this.prev and this.next 换成了this.left and this.right.

2. 定义一棵二叉树，它应该包含 - 一个根节点，以及上面提到的常见操作方法，这里我们用Class来实现

   
       class BinarySearchTree {
           constructor() {
               this.root = null;
           }
       }
   

3. 实现插入操作

• 如果根不存在，则新插入节点直接作为根
• 否则，从根节点开始递归直到找到应该插入的位置

  
       // 向树插入一个新键
    insert(key, currentNode = this.root) {
      if (!this.root) {
        this.root = new Node(key);
      } else {
        this.insertNode(key, this.root);
      }
    }
  
      // 找到新节点应该插入的位置
    insertNode(key, node) {
      if (this.compareFn(key, node.key) === CompareResult.LESS_THAN) {
        if (!node.left) {
          node.left = new Node(key);
          return;
        } else {
          this.insertNode(key, node.left);
        }
      } else {
        if (!node.right) {
          node.right = new Node(key);
          return;
        } else {
          this.insertNode(key, node.right);
        }
      }
    }

4. 中序遍历

   
   // 中序遍历 - 根节点位于左子树节点与右子树节点中间，先访问左节点，再访问根节点，最后访问右节点
     inorderTreeWalk() {
       this.inorderNode(this.root);
     }
     inorderNode(node) {
       if (node !== null) {
         this.inorderNode(node.left);
         console.log(node.key);
         this.inorderNode(node.right);
       }
       return undefined;
     }
   
   

5. 先序遍历

   
       // 先序遍历 - 根节点位于左右子树节点之前，先访问父节点后访问左、右子节点
     preorderTreeWalk() {
       this.preorderNode(this.root);
     }
   
     preorderNode(node) {
       if (node !== null) {
         console.log(node.key);
         this.preorderNode(node.left);
         this.preorderNode(node.right);
       }
       return undefined;
     }
   

6. 后序遍历

   
     // 后序遍历 - 根节点位于左右子树节点之后,先访问左、右子节点后访问父节点
     postorderTreeWalk() {
       this.postorderNode(this.root);
     }
   
     postorderNode(node) {
       if (node !== null) {
         this.postorderNode(node.left);
         this.postorderNode(node.right);
         console.log(node.key);
       }
       return;
     }

7. 删除某个节点

• 先递归找到要删除的节点

• 若节点没有左右子树（叶节点），则可以直接删除

• 若节点仅有一棵子树，则删除当前节点并将子树上移

• 若节点有左右子树，则找到右子树的最小值来替代要当前节点（或左子树的最大值），然后再删除右子树中的最小值

  
     // 移除一个节点
    remove(key) {
      return this.removeNode(key, this.root);
    }
  
    removeNode(key, current) {
      if (this.compareFn(key, current.key) === CompareResult.LESS_THAN) {
        current.left = this.removeNode(key, current.left);
        return current;
      } else if (
        this.compareFn(key, current.key) === CompareResult.GREATER_THAN
      ) {
        current.right = this.removeNode(key, current.right);
        return current;
      } else {
        // 没有子树，则直接删除
        if (!current.left && !current.right) {
          current = null;
          return current;
        }
       // 只有一棵子树，子树上移
        if (!current.left) {
          current = current.right;
          return current;
        } else if (!current.right) {
          current = current.left;
          return current;
        }
       // 左右子树都有的情况
        const minNode = this.minNode(current.right);
        current.key = minNode.key;
        current.right = this.removeNode(minNode.key, current.right);
        return current;
      }
    }
  
  

…
其它操作方法的实现，可以参考我的codepen

See the Pen BST by JinZhang (@jackzong) on CodePen.

二叉树在计算机科学中的应用

• 利用中序遍历对一组数进行排序
• 待定。。。

其它知识点

• 树的顶部节点 - 根节点
• 没有子元素的节点 - 叶节点
• 树的最小键存在于左子树的最左端点
• 树的最大键存在于右子树的最右端点
• 树的节点有个属性叫深度，其值是所有祖先节点的数量
• 树的高度：
  • 根节点到最远叶子节点的最长路径上的边数（这是教科书上比较标准的定义，LeetCode上习惯定义为：根节点到最远叶子节点的最长路径上的节点数，所以LeetCode的树都会多一层:)；
  • 或者可以用分层理论去看一棵树的高度，根节点处于第一层，叶节点处于最后一层，层数即为树的高度；