如何对树状结构的数据进行操作

Question

现有数据如下

var tree = {
  id: 0,
  pid: -1,
  name: '0',
  children: [
    { id: 1, pid: 0, name: '1' },
    { id: 2, pid: 0, name: '2' },
    {
      id: 3, pid: 0, name: '3', children: [
        { id: 4, pid: 3, name: '4', children: [...] },
        { id: 5, pid: 3, name: '5', children: [...] }
      ]
    }
    .
    .
    .
  ]
}

id是唯一标识符，生成时可以用new Date().getTime()替代
需求：1.任意一个节点都可以插入新的子节点；2.任意一个节点都可以删除（可以只删掉本节点，也可以连同子节点一起删除）；
有什么好的算法去操作这个数据对象呢？

Answer 1

你可以将目前的这个数据结构打平，每个节点都压入数组arr中，之前的children改为保留对应子节点id的数组，然后数组arr按照id排序，这样通过第一个节点（根节点）的children就可以遍历出所有子节点。插入节点只需根据id插入到arr对应的位置（插入排序即可），删除节点只需根据id找到节点，递归遍历子节点全部从arr中删除即可。由于数组有序，查找单个节点可以简单的用二分法快速找到。

Answer 2

这个问题要看具体的需要，是需要省空间，还是需要省时间。
还有具体哪些操作比较重要，比如从父寻子，从子寻父要求的结构就不一样。

以下是一些伪代码样例：

格式样例1:

struct Node<T> {
  id: Int;
  val: T;
  children: Array<Node*>;
}

typedef List = Array<Node>;

格式样例2：

struct Node<T> {
  id: Int;
  val: T;
  parent: Node*;
};

typedef List = Array<Node>;

格式样例3:

struct Node<T> {
  id: Int;
  val: T;
  parent: Node*；
  children: Array<Node*>;
};

typedef List = HashMap<Int, Node*>;