js分类树

JavaScript中的分类树（也称为树形结构或树数据结构）是一种非线性数据结构，它模拟了一种层次关系，就像一棵倒置的树，有一个根节点，每个节点可以有零个或多个子节点。

基础概念

节点（Node）：树的基本单元，包含数据和指向其子节点的引用。
根节点（Root Node）：树的起始点，没有父节点。
子节点（Child Node）：一个节点的直接后继节点。
父节点（Parent Node）：一个节点的直接前驱节点。
兄弟节点（Sibling Node）：具有相同父节点的两个节点。
叶节点（Leaf Node）：没有子节点的节点。
深度（Depth）：从根节点到特定节点的最长路径上的边数。
高度（Height）：从特定节点到其最远叶节点的最长路径上的边数。

类型

二叉树（Binary Tree）：每个节点最多有两个子节点。
二叉搜索树（Binary Search Tree）：左子树上所有节点的值都小于其根节点的值，右子树上所有节点的值都大于其根节点的值。
N叉树（N-ary Tree）：每个节点可以有N个子节点。

应用场景

文件系统：文件和目录的结构。
DOM树：网页的结构，其中每个元素都是一个节点。
路由算法：在网络中找到最佳路径。
组织结构图：公司或团队的层级结构。

示例代码

以下是一个简单的JavaScript实现二叉树的例子：

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  inOrderTraverse(node = this.root, callback) {
    if (node !== null) {
      this.inOrderTraverse(node.left, callback);
      callback(node.value);
      this.inOrderTraverse(node.right, callback);
    }
  }
}

// 使用示例
const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

tree.inOrderTraverse((value) => console.log(value)); // 输出: 3 5 7 10 15

可能遇到的问题及解决方法

问题：树不平衡导致搜索效率低下。

原因：在二叉搜索树中，如果插入的数据是有序的，树会退化成一个链表，导致搜索、插入和删除操作的时间复杂度退化到O(n)。

解决方法：

使用自平衡二叉搜索树，如AVL树或红黑树。
在插入和删除操作后进行旋转以保持树的平衡。

示例代码（AVL树旋转）：

class AVLNode extends TreeNode {
  constructor(value) {
    super(value);
    this.height = 1;
  }
}

class AVLTree extends BinaryTree {
  // ...其他方法

  getBalanceFactor(node) {
    return node === null ? 0 : this.getHeight(node.left) - this.getHeight(node.right);
  }

  getHeight(node) {
    return node === null ? 0 : node.height;
  }

  updateHeight(node) {
    node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
  }

  rotateRight(y) {
    let x = y.left;
    let T2 = x.right;

    x.right = y;
    y.left = T2;

    this.updateHeight(y);
    this.updateHeight(x);

    return x;
  }

  rotateLeft(x) {
    let y = x.right;
    let T2 = y.left;

    y.left = x;
    x.right = T2;

    this.updateHeight(x);
    this.updateHeight(y);

    return y;
  }

  insertNode(node, newNode) {
    // ...之前的插入逻辑

    let balanceFactor = this.getBalanceFactor(node);

    // Left Left Case
    if (balanceFactor > 1 && newNode.value < node.left.value) {
      return this.rotateRight(node);
    }

    // Right Right Case
    if (balanceFactor < -1 && newNode.value > node.right.value) {
      return this.rotateLeft(node);
    }

    // Left Right Case
    if (balanceFactor > 1 && newNode.value > node.left.value) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }

    // Right Left Case
    if (balanceFactor < -1 && newNode.value < node.right.value) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }
}

以上代码展示了如何在JavaScript中实现一个基本的二叉搜索树，并通过AVL树的旋转操作来解决不平衡问题。