树的操作

基础

遍历:

• child::普通树的遍历
• child::森林的遍历

删除节点

child::

删除树节点

方法之一

• 遍历树的时候，缓存其当前节点的父节点
• 从父节点中移除当前节点

方法之一

• 遍历树的同时复制一棵树，对于需要删除的节点，则不复制
• 缺点：需要两倍的空间
• 优点：方便快捷

指向原始笔记的链接

克隆

child::

克隆树

• child::

  广度优先克隆树

  在 JavaScript 中，可以使用广度优先搜索（BFS）来实现树的深拷贝。下面是一个实现的示例：

  class TreeNode {
      constructor(value) {
          this.value = value;
          this.children = [];
      }
      
      addChild(child) {
          this.children.push(child);
      }
  }
  function deepCopyTree(root) {
      if (!root) {
          return null; // 如果根节点为空，返回 null
      }
      // 创建一个队列用于广度优先遍历
      const queue = [];
      const clonedRoot = new TreeNode(root.value); // 复制根节点
      queue.push({ original: root, clone: clonedRoot }); // 将原始节点和克隆节点放入队列
      while (queue.length > 0) {
          const { original, clone } = queue.shift(); // 弹出队列中的第一个元素
          // 遍历当前节点的子节点
          for (const child of original.children) {
              const clonedChild = new TreeNode(child.value); // 复制子节点
              clone.children.push(clonedChild); // 将复制的子节点添加到克隆节点的子节点中
              queue.push({ original: child, clone: clonedChild }); // 将子节点的原始和克隆放入队列
          }
      }
      return clonedRoot; // 返回深拷贝的树的根节点
  }
  // 示例用法
  const root = new TreeNode(1);
  const child1 = new TreeNode(2);
  const child2 = new TreeNode(3);
  const child3 = new TreeNode(4);
  root.addChild(child1);
  root.addChild(child2);
  child1.addChild(child3);
  const clonedTree = deepCopyTree(root);
  // 打印结果以验证深拷贝
  console.log(clonedTree); // 输出克隆的树结构

  指向原始笔记的链接

• child::

  深度优先克隆树

  伪代码

  function cloneTree(tree){
      function dfs(node){
          let cloneNode = clone(node)
          cloneNode.children= tree.children.map(v=>dfs(v))
          return cloneNode
      }
      return dfs(tree)
  }

  指向原始笔记的链接

指向原始笔记的链接