js树实现

树的基本概念

树是一种非线性的数据结构，由节点和边组成。每个节点包含一个值和指向子节点的引用。树的顶部节点称为根节点，没有子节点的节点称为叶节点。

树的实现方式

在JavaScript中，树可以通过对象或类来实现。以下是两种常见的实现方式：

使用对象字面量

const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: []
    },
    {
      value: 3,
      children: [
        {
          value: 4,
          children: []
        }
      ]
    }
  ]
};

使用类

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(childNode) {
    this.children.push(childNode);
  }
}

const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const grandChild = new TreeNode(4);

root.addChild(child1);
root.addChild(child2);
child2.addChild(grandChild);

树的遍历方法

树的遍历是指访问树中所有节点的过程。常见的遍历方式有深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历（DFS）

function dfs(node) {
  console.log(node.value);
  node.children.forEach(child => dfs(child));
}

广度优先遍历（BFS）

function bfs(root) {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value);
    node.children.forEach(child => queue.push(child));
  }
}

二叉树实现

二叉树是每个节点最多有两个子节点的树结构。

二叉树节点类

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

二叉搜索树插入

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

  insert(value) {
    const newNode = new BinaryTreeNode(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);
      }
    }
  }
}

树的常见操作

查找节点、删除节点、计算深度等是树的常见操作。

查找节点

function findNode(root, value) {
  if (root === null) return null;
  if (root.value === value) return root;
  for (const child of root.children) {
    const found = findNode(child, value);
    if (found) return found;
  }
  return null;
}

计算树深度

function treeDepth(node) {
  if (node === null) return 0;
  let maxDepth = 0;
  node.children.forEach(child => {
    maxDepth = Math.max(maxDepth, treeDepth(child));
  });
  return maxDepth + 1;
}