C#构建树形结构数据(全部构建,查找构建)_c#

摘要：

最近在做任务管理，任务可以无限派生子任务且没有数量限制，前端采用easyui的treegrid树形展示控件。

一、遇到的问题

获取全部任务拼接树形速度过慢(数据量大约在900条左右)且查询速度也并不快；

二、解决方法

1、tree转化的json数据格式

a.json数据格式：

[
  {
    "children":[
      {
        "children":[

        ],
        "username":"username2",
        "password":"password2",
        "id":"2",
        "pid":"1",
        "name":"节点2"
      },
      {
        "children":[

        ],
        "username":"username2",
        "password":"password2",
        "id":"a2",
        "pid":"1",
        "name":"节点2"
      }
    ],
    "username":"username1",
    "password":"password1",
    "id":"1",
    "pid":"0",
    "name":"节点1"
  },
  {
    "children":[

    ],
    "username":"username1",
    "password":"password1",
    "id":"a1",
    "pid":"0",
    "name":"节点1"
  }
]

b.定义实体必要字段

为了tree结构的通用性，我们可以定义一个抽象的公用实体treeobject以保证后续涉及到的list<t>转化树形json

using system;
using system.collections.generic;
using system.linq;
using system.text;
using system.threading.tasks;

namespace mytree.abs
{
  public abstract class treeobejct
  {
    public string id { set; get; }
    public string pid { set; get; }
    public string name { set; get; }
    public ilist<treeobejct> children = new list<treeobejct>();
    public virtual void addchildren(treeobejct node)
    {
      this.children.add(node);
    }
  }
}

c.实际所需实体treemodel让它继承treeobject,这样对于id,pid,name,children我们就可以适用于其它实体了，这也相当于我们代码的特殊约定：

using mytree.abs;
using system;
using system.collections.generic;
using system.linq;
using system.text;
using system.threading.tasks;

namespace mytree.models
{
  public class treemodel : treeobejct
  {
    public string username { set; get; }
    public string password { set; get; }
  }
}

2、递归遍历

获取全部任务并转化为树形

获取全部任务转化为树形是比较简单的，我们首先获取到pid=0的顶级数据(即不存在父级的任务),我们通过顶级任务依次递归遍历它们的子节点。

b.我们暂时id以1开始则pid=0的都为顶级任务

我们首先写一段生成数据的方法：

    public static ilist<treeobejct> getdata(int number = 11)
    {
      ilist<treeobejct> datas = new list<treeobejct>();
      for (int i = 1; i < number; i++)
      {
        datas.add(new treemodel
        {
          id = i.tostring(),
          pid = (i - 1).tostring(),
          name = "节点" + i,
          username = "username" + i,
          password = "password" + i
        });
        datas.add(new treemodel
        {
          id = "a" + i.tostring(),
          pid = (i - 1).tostring(),
          name = "节点" + i,
          username = "username" + i,
          password = "password" + i
        });
      }
      return datas;
    }

其次我们定义一些变量：

    private static ilist<treeobejct> models;
    private static ilist<treeobejct> models2;
    private static thread t1;
    private static thread t2;
    static void main(string[] args)
    {
      int count = 21;
      console.writeline("生成任务数："+count+"个");
     
      console.read();
    }

我们再写一个递归获取子节点的递归方法：

    public static ilist<treeobejct> getchildrens(treeobejct node)
    {
      ilist<treeobejct> childrens = models.where(c => c.pid == node.id.tostring()).tolist();
      foreach (var item in childrens)
      {
        item.children = getchildrens(item);
      }
      return childrens;

    }

编写调用递归方法recursion：

    public static void recursion()
    {
      #region 递归遍历
      system.diagnostics.stopwatch sw = new system.diagnostics.stopwatch();

      sw.start();

      var mds_0 = models.where(c => c.pid == "0");//获取顶级任务
      foreach (var item in mds_0)
      {
        item.children = getchildrens(item);
      }
      sw.stop();
      console.writeline("----------递归遍历用时：" + sw.elapsedmilliseconds + "----------线程名称："+t1.name+",线程id："+t1.managedthreadid);

      #endregion
    }

编写main函数启动测试：

    private static ilist<treeobejct> models;
    private static ilist<treeobejct> models2;
    private static thread t1;
    private static thread t2;
    static void main(string[] args)
    {
      int count = 1001;
      console.writeline("生成任务数："+count+"个");
      models = getdata(count);
     
      t1 = new thread(recursion);
     
      t1.name = "递归遍历";
      t1.start();
    

      console.read();
    }

输出结果：

递归遍历至此结束。

3、非递归遍历

非递归遍历在操作中不需要递归方法的参与即可实现tree的拼接

对于以上的代码，我们不需要修改，只需要定义一个非递归遍历方法notrecursion：

    public static void notrecursion()
    {
      #region 非递归遍历

      system.diagnostics.stopwatch sw2 = new system.diagnostics.stopwatch();

      sw2.start();
      dictionary<string, treeobejct> dtomap = new dictionary<string, treeobejct>();
      foreach (var item in models)
      {
        dtomap.add(item.id, item);
      }
      ilist<treeobejct> result = new list<treeobejct>();
      foreach (var item in dtomap.values)
      {
        if (item.pid == "0")
        {
          result.add(item);
        }
        else
        {
          if (dtomap.containskey(item.pid))
          {
            dtomap[item.pid].addchilrden(item);
          }
        }


      }

      sw2.stop();
      console.writeline("----------非递归遍历用时：" + sw2.elapsedmilliseconds + "----------线程名称：" + t2.name + ",线程id：" + t2.managedthreadid);

      #endregion
    }

编写main函数：

    private static ilist<treeobejct> models;
    private static ilist<treeobejct> models2;
    private static thread t1;
    private static thread t2;
    static void main(string[] args)
    {
      int count = 6;
      console.writeline("生成任务数："+count+"个");
      models = getdata(count);
      models2 = getdata(count);
      t1 = new thread(recursion);
      t2 = new thread(notrecursion);
      t1.name = "递归遍历";
      t2.name = "非递归遍历";
      t1.start();
      t2.start();

      console.read();
    }

启动查看执行结果：

发现一个问题，递归3s，非递归0s，随后我又进行了更多的测试：

执行时间测试

任务个数	递归(ms)	非递归(ms)
6	3	0
6	1	0
6	1	0
101	1	0
101	4	0
101	5	0
1001	196	5
1001	413	1
1001	233	7
5001	4667	5
5001	4645	28
5001	5055	7
10001	stackoverflowexception	66
10001	stackoverflowexception	81
10001	stackoverflowexception	69
50001	-	46
50001	-	47
50001	-	42
100001	-	160
100001	-	133
100001	-	129