树算法

基本的二叉树不介绍了。

深度优先遍历、广度优先遍历单独拿出来。

DOM树查询类名

function queryClassName(node, name) {
  // 辅助函数：遍历节点和全部子节点
  let walkTheDOM = function(node, func) {
    func(node);
    node = node.firstChild;
    while (node) {
      walkTheDOM(node, func);
      node = node.nextSibling;
    }
  }
  let starts = '(^|[ \n\r\t\f])', ends = '([ \n\r\t\f]|$)';
  let regex = new RegExp(starts + name + ends);
  let results = [];

  // 处理函数：把满足类名条件的节点放到结果数组
  let callback = function (currentNode) {
    if (regex.test(currentNode.className)) {
      results.push(currentNode);
    }
  }
  // 递归遍历Node节点
  walkTheDOM(node, callback);
  return results;
}

二叉搜索树

Binary Search Tree(BST or Ordered Binary Tree)

插入和删除相对复杂，查找遍历比较简单

class Node {

  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  show() {
    return this.data;
  }
}


class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  // 插入值
  insert(data) {
    // 创建一个节点
    let n = new Node(data, null, null);
    // 如果没有根节点，那么直接作为根节点
    if (!this.root) {
      return this.root = n;
    }
    let currentNode = this.root;
    let parent = null;
    // 循环，直到找到一个节点是空，然后把这个节点放在这里（重复节点？）
    while (1) {
      parent = currentNode;
      if (data < currentNode.data) {
        currentNode = currentNode.left;
        if (currentNode === null) {
          parent.left = n;
          break;
        }
      } else {
        currentNode = currentNode.right;
        if (currentNode === null) {
          parent.right = n;
          break;
        }
      }
    }
  }

  // 删除值（外部调用）
  remove(data) {
    this.root = this.removeNode(this.root, data)
  }

  // 删除节点（内部调用）
  removeNode(node, data) {
    // 如果节点是空，直接返回
    if (node == null) {
      return null;
    }

    // 如果当前节点的值是删除的值
    if (data == node.data) {
      // no children node
      // 删除这个节点，并把左子节点或者右子节点改成当前节点（指针指向左子树或者右子树）
      if (node.left == null && node.right == null) {
        return null;
      }
      if (node.left == null) {
        return node.right;
      }
      if (node.right == null) {
        return node.left;
      }

      // 辅助函数 找到子树中最小值的节点
      let getSmallest = function(node) {
        if(node.left === null && node.right == null) {
          return node;
        }
        if(node.left != null) {
          return node.left;
        }
        if(node.right !== null) {
          return getSmallest(node.right);
        }
      };

      // 如果当前的节点的值是目标值，那么找到右子树中最小的节点
      let temNode = getSmallest(node.right);
      // 把当前的节点的值改成右子树最小的值
      node.data = temNode.data;
      // 删除右子树中最小节点
      node.right = this.removeNode(temNode.right,temNode.data);
      return node;
    }
    // 如果当前节点的值大于或者小于目标值，递归找子节点的值
    else if (data < node.data) {
      node.left = this.removeNode(node.left,data); 
      return node;
    }
    else {
      node.right = this.removeNode(node.right,data);  
      return node;
    }
  }

  // 查找：如果当前节点值小于目标值，那么就找左子树；否则就找右子树
  find(data) {
    var current = this.root;
    while (current != null) {
      if (data == current.data) {
        break;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right
      }
    }
    return current.data;
  }

  // 获取最大值（右侧子节点）
  findMax() {
    var current = this.root;
    while (current.right != null) {
      current = current.right;
    }
    return current.data;
  }

  // 获取最小值（左侧子节点）
  findMin() {
    var current = this.root;
    while (current.left != null) {
      current = current.left;
    }
    return current.data;
  }

  // 中序遍历
  inOrder(node) {
    if (!this.inOrderArr) {
      this.inOrderArr = [];
    }
    if (node !== null) {
      this.inOrder(node.left);
      this.inOrderArr.push(node.data);
      this.inOrder(node.right);
    }
  }

  // 前序遍历
  preOrder(node) {
    if (!this.preOrderArr) {
      this.preOrderArr = [];
    }
    if (node !== null) {
      this.preOrderArr.push(node.data);
      this.preOrder(node.left);
      this.preOrder(node.right);
    }
  }

    // 后续遍历
  postOrder(node) {
    if (!this.postOrderArr) {
      this.postOrderArr = [];
    }
    if (node !== null) {
      this.postOrder(node.left);
      this.postOrder(node.right);
      this.postOrderArr.push(node.data);
    }
  }

}

---

Last update: May 28, 2021