javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】

Javascript数据结构之多叉树经典操作示例

什么是多叉树

多叉树是一种树形数据结构，每个节点可以有多个子节点。多叉树有很多应用场景，比如组织结构图、文件系统等。

多叉树的创建

多叉树可以通过对象字面量的方法创建。对于每个节点，需要至少包含一个value和一个children属性，分别表示节点的值和子节点数组。

let tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 3, children: [] },
        { value: 4, children: [] }
      ]
    },
    {
      value: 5,
      children: [
        { value: 6, children: [] },
        { value: 7, children: [] }
      ]
    }
  ]
}

多叉树的添加

向多叉树中添加节点，需要先找到要添加节点的位置。下面是向多叉树中添加新节点的示例代码。

function addChild(tree, value, parentValue) {
  if (tree.value === parentValue) {
    tree.children.push({ value: value, children: [] })
    return
  }
  for (let i = 0; i < tree.children.length; i++) {
    addChild(tree.children[i], value, parentValue)
  }
}

该函数接受三个参数：多叉树tree、要添加的节点值value、要添加到的父节点值parentValue。

多叉树的遍历

多叉树的遍历有很多种方法，例如深度优先遍历、广度优先遍历等。下面是广度优先遍历的示例代码。

function breadthFirstSearch(tree) {
  let queue = [tree]
  while (queue.length > 0) {
    let node = queue.shift()
    console.log(node.value)
    for (let i = 0; i < node.children.length; i++) {
      queue.push(node.children[i])
    }
  }
}

该函数接受一个参数：多叉树tree。使用一个队列来存储待遍历的节点，初始时将根节点加入队列。每次从队列头部取出一个节点进行处理，将该节点的子节点加入队列尾部。直到队列为空时，遍历结束。

多叉树的移除

从多叉树中移除节点，需要先找到要移除节点及其父节点。下面是从多叉树中移除节点的示例代码。

function removeNode(tree, value, parentValue) {
  if (tree.value === parentValue) {
    for (let i = 0; i < tree.children.length; i++) {
      if (tree.children[i].value === value) {
        tree.children.splice(i, 1)
        return true
      }
    }
  } else {
    for (let i = 0; i < tree.children.length; i++) {
      if (removeNode(tree.children[i], value, parentValue)) {
        return true
      }
    }
  }
  return false
}

该函数接受三个参数：多叉树tree、要移除的节点值value、要移除的节点的父节点值parentValue。

上述为多叉树创建、添加、遍历、移除的基础操作。以下是两条示例说明：

示例1： 向多叉树中添加节点

let tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 3, children: [] },
        { value: 4, children: [] }
      ]
    },
    {
      value: 5,
      children: [
        { value: 6, children: [] },
        { value: 7, children: [] }
      ]
    }
  ]
}

addChild(tree, 8, 4)

/**
 * 添加节点8到节点4的子节点中
 * 添加后的多叉树结构：
 * {
 *   value: 1,
 *   children: [
 *     {
 *       value: 2,
 *       children: [
 *         { value: 3, children: [] },
 *         { value: 4, children: [{ value: 8, children: [] }] }
 *       ]
 *     },
 *     {
 *       value: 5,
 *       children: [
 *         { value: 6, children: [] },
 *         { value: 7, children: [] }
 *       ]
 *     }
 *   ]
 * }
 */

示例2： 从多叉树中移除节点

let tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 3, children: [] },
        { value: 4, children: [] }
      ]
    },
    {
      value: 5,
      children: [
        { value: 6, children: [] },
        { value: 7, children: [] }
      ]
    }
  ]
}

removeNode(tree, 4, 2)

/**
 * 移除节点4
 * 移除后的多叉树结构：
 * {
 *   value: 1,
 *   children: [
 *     {
 *       value: 2,
 *       children: [
 *         { value: 3, children: [] }
 *       ]
 *     },
 *     {
 *       value: 5,
 *       children: [
 *         { value: 6, children: [] },
 *         { value: 7, children: [] }
 *       ]
 *     }
 *   ]
 * }
 */