js实现tree

实现树结构的基本方法

使用JavaScript实现树结构通常需要定义节点类和树类。树结构由多个节点组成，每个节点包含数据和指向子节点的引用。

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

  addChild(child) {
    if (child instanceof TreeNode) {
      this.children.push(child);
    } else {
      this.children.push(new TreeNode(child));
    }
  }
}

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

  traverseDF(callback) {
    const traverse = (node) => {
      callback(node);
      node.children.forEach(child => traverse(child));
    };
    traverse(this.root);
  }

  traverseBF(callback) {
    const queue = [this.root];
    while (queue.length > 0) {
      const node = queue.shift();
      callback(node);
      queue.push(...node.children);
    }
  }
}

树的遍历方法

深度优先遍历(DFS)和广度优先遍历(BFS)是树结构的两种基本遍历方式。DFS会沿着树的深度遍历子节点，BFS会按层级遍历节点。

// 深度优先搜索示例
const dfs = (node) => {
  console.log(node.data);
  node.children.forEach(child => dfs(child));
};

// 广度优先搜索示例
const bfs = (root) => {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.data);
    queue.push(...node.children);
  }
};

树的操作方法

树结构支持多种操作，包括查找节点、删除节点、计算深度等。

// 查找节点
Tree.prototype.find = function(data, traversal) {
  let result = null;
  traversal.call(this, (node) => {
    if (node.data === data) {
      result = node;
    }
  });
  return result;
};

// 计算树的高度
Tree.prototype.getHeight = function() {
  const getMaxDepth = (node) => {
    if (!node || node.children.length === 0) return 0;
    const depths = node.children.map(child => getMaxDepth(child));
    return Math.max(...depths) + 1;
  };
  return getMaxDepth(this.root);
};

二叉树实现

二叉树是每个节点最多有两个子节点的树结构，常用于搜索和排序算法。

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

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

  insert(value) {
    const newNode = new BinaryTreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }
}

树的可视化表示

将树结构转换为可视化格式有助于调试和理解树的状态。

Tree.prototype.toString = function() {
  const lines = [];
  const traverse = (node, prefix) => {
    lines.push(prefix + node.data);
    node.children.forEach((child, i) => {
      const isLast = i === node.children.length - 1;
      traverse(child, prefix + (isLast ? '└── ' : '├── '));
    });
  };
  traverse(this.root, '');
  return lines.join('\n');
};