mysql存储的文件结构体_如何存储一颗树到文件或者数据库

也就是序列化存储一棵树，不管是存储到数据库，还是存储到文件，都可以使用树的基本遍历方式序列化存储再反序列化构造。但是考察使用数据库存储时肯定还希望存储以后实现更高级的功能，如快速查询某个节点的所有子节点。

下面给出存储到文件与存储到 DB 的具体方案和代码

树结构体

public class TreeNode {

int val = 0;

TreeNode left = null;

TreeNode right = null;

public TreeNode(int val) {

this.val = val;

}

}

存储到文件

假设是一颗二叉树，那直接就先序遍历序列化存储了，为了更加适用于普通的多叉树，我还在后面添加了更为普遍的多叉树的序列化代码。

下面会把一棵树系列化成一个字符串，例如：2,3,#,4,5

# 号代表的是 null 节点

得到该字符串后可以存储到文件、也可以存储到 DB，也可以通过网络传输出去等等

/*通过 LDR 和 DLR 可以恢复一棵二叉树序列化成 DLR 可以便于反序列化，因为第一个节点就是根节点。反序列化的时候可以根据读出的每个节点构建树*/

StringBuffer buffer = new StringBuffer();

String Serialize(TreeNode root) {

if (root == null) {

buffer.append("#,");

return buffer.toString();

}

buffer.append(root.val + ",");

Serialize(root.left);

Serialize(root.right);

return buffer.toString();

}

int i = -1;

// 注意指针的指向 TreeNode Deserialize(String str) {

i++;

TreeNode root = null;

if (str == null || str.length() == 0)

return root;

String[] nodes = str.split(",");

if (!nodes[i].equals("#")) {

root = new TreeNode(Integer.valueOf(nodes[i]));

// 恢复先序遍历的结果的时候也要先从左孩子开始 root.left = Deserialize(str);

root.right = Deserialize(str);

}

return root;

}

更为一般的树的序列化和反序列化

// 首先是树的结构体public static class TreeNode {

int val = 0;

TreeNode left = null;

TreeNode right = null;

TreeNode center = null; // =》》 加了一个字节点

public TreeNode(int val) {

this.val = val;

}

}

// 然后是序列化与反序列化代码/********* 层序遍历 *************/

public static String serialize(TreeNode root) {

if (null == root) {

return "";

}

// 使用队列存储下一层节点 LinkedList queue = new LinkedList<>();

StringBuilder builder = new StringBuilder();

queue.add(root);

while (!queue.isEmpty()) {

// 处理每一个节点的时候，都要把该节点的子节点放入队尾，等待下一次被取出读取 TreeNode node = queue.removeFirst();

if (node != null) {

builder.append(node.val);

queue.addLast(node.left);

queue.addLast(node.center);

queue.addLast(node.right);

} else {

builder.append("#");

}

builder.append(",");

}

// 去掉最后一个 , 号 builder.deleteCharAt(builder.length() - 1);

return builder.toString();

}

public static TreeNode deserialize(String data) {

if (null == data || data.isEmpty()) {

return null;

}

String[] nodes = data.split(",");

int index = 0;

TreeNode root = buildNode(nodes[index++]);

LinkedList queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

TreeNode node = queue.removeFirst();

node.left = buildNode(nodes[index++]);

node.center = buildNode(nodes[index++]);

node.right = buildNode(nodes[index++]);

if (node.left != null) {

queue.addLast(node.left);

}

if (node.center != null) {

queue.addLast(node.left);

}

if (node.right != null) {

queue.addLast(node.right);

}

}

return root;

}

private static TreeNode buildNode(String node) {

if ("#".equals(node)) {

return null;

}

return new TreeNode(Integer.valueOf(node));

}

public static void main(String[] args) {

TreeNode n1 = new TreeNode(1);

TreeNode n2 = new TreeNode(2);

TreeNode n3 = new TreeNode(3);

TreeNode n4 = new TreeNode(4);

TreeNode n5 = new TreeNode(5);

TreeNode n6 = new TreeNode(6);

n1.left = n2;

n1.right = n3;

n1.center = n5;

n3.left = n4;

n3.right = n6;

String ans = serialize(n1);

System.out.println(ans);

TreeNode root = deserialize(ans);

}

存储到数据库

上面提到的是将任意一种树序列化之后存储或者发送出去，下面要求存储到数据库里面，并实现更多高级功能。例如：快速找到某个节点的子节点

将树存储到数据库是一个非常常见且实用的操作，例如把下图这样一个组织架构图存储到DB中

存储完了之后还要实现如下高级功能：查询小天的直接上司。

查询老宋管理下的直属员工。

查询小天的所有上司。

查询老王管理的所有员工。

方案一：存储节点以及他的父节点信息

这是最常用的方案(也是存在很多局限的方法)，存储到 DB 之后结果如图：

以上四个问题的答案：查询小天的直接上司。SELECT e2.eid,e2.ename FROM employees e1,employees e2 WHERE e1.parent_id=e2.eid AND e1.ename='小天';

查询老宋管理下的直属员工。SELECT e1.eid,e1.ename FROM employees e1,employees e2 WHERE e1.parent_id=e2.eid AND e2.ename='老宋';

查询小天的所有上司。如果数据库不支持递归查询的话，这里没法直接查，只能进行循环查询，先查直接上司，再查直接上司的直接上司，依次循环。

可以业务代码层实现循环查询。

也可以通过存储过程实现。

查询老王管理的所有员工。先获取所有父节点为老王id的员工id，然后将员工姓名加入结果列表里。在将这些员工的id作为父节点再次查询一遍，循环处理即可

方法二：闭包表

该方法记录了树中所有节点的关系，不仅仅只是直接父子关系，它需要使用2张表，除了节点表本身之外，还需要使用1张表来存储节祖先点和后代节点之间的关系(同时增加一行节点指向自身),并且根据需要，可以增加一个字段，表示深度。因此这种方法数据量很多。设计的表结构如下：

Tree 表结构，两个字段：节点 id 和节点内容

NodeRelation 表结构，三个字段：祖先节点、后继节点、节点深度

可以看到，NodeRelation 表的数据量很多。但是查询非常方便。

比如，要查询 D 节点的子元素，只需要：select * from NodeRelation where ancestor=4;

要查询节点 D 的直接子节点，则直接加上depth=1 即可：select * from NodeRelation where ancestor=4 and depth=1;

要查询节点 J 的所有父节点：select * from NodeRelation where descendant=10;

如果是插入一个新的节点，比如在L节点后添加子节点M，则插入的节点除了M自身外，还有对应的节点关系。即还有哪些节点和新插入的M节点有后代关系。这个其实很简单，只要和L节点有后代关系的，和M节点必定会有后代关系，并且和L节点深度为X的和M节点的深度必定为X+1。因此，在插入M节点后，找出L节点为后代的那些节点作为和M节点之间有后代关系，插入到数据表。

INSERT INTO tree3 (value) VALUES('M'); -- 插入节点INSERT INTO NodeRelation(ancestor,descendant,depth)

select n.ancestor,last_insert_rowid(),n.depth+1 -- 此处深度+1作为和M节点的深度from NodeRelation n

where n.descendant=12

Union ALL

select last_insert_rowid() ,last_insert_rowid(),0 --加上自身

在某些并不需要使用深度的情况下，甚至可以不需要depth字段。

如果要删除某个节点也很容易，比如，要删除节点D，这种情况下，除了删除tree3表中的D节点外，还需要删除NodeRelation表中的关系。

首先以D节点为后代的关系要删除，同时以D节点的后代为后代的这些关系也要删除：

delete from NodeRelation where descendant in

(select descendant from NodeRelation where ancestor=4 )；

--查询以D节点为祖先的那些节点，即D节点的后代。

这种删除方法，虽然彻底，但是它也删除了D节点和它原本的子节点的关系。

如果只是想割裂D节点和A节点的关系，而对于它原有的子节点的关系予以保留，则需要加入限定条件。

限制要删除的关系的祖先不以D为祖先，即如果这个关系以D为祖先的，则不用删除。因此把上面的SQL加上条件。

delete from NodeRelation where descendant in

(select descendant from NodeRelation where ancestor=4 )；

--查询以D节点为祖先的那些节点，即D节点的后代。

and ancestor not in (select descendant from NodeRelation where ancestor =4 )

上面的SQL用文字描述就是，查询出D节点的后代，如果一个关系的祖先不属于D节点的后代，并且这个关系的后代属于D节点的后代，就删除它。

这样的删除，保留了D节点自身子节点的关系，如上面的例子，实际上删除的节点关系为：

如果要删除节点H，则为