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，随后我又进行了更多的测试：

执行时间测试

StackOverflowException:因包含的嵌套方法调用过多而导致执行堆栈溢出时引发的异常。 此类不能被继承。

StackOverflowException 执行堆栈溢出发生错误时引发，通常发生非常深度或无限递归。

-:没有等到结果。

当然这个测试并不专业，但是也展示出了它的效率的确满足了当前的需求。

4、查找构建树形结果

原理同上述非递归相同，不同之处是我们通过查找的数据去构建树形

我们通过查找获取到圈中的任务,再通过当前节点获取到父级节点，因为当时没考虑到任务层级的关系，因此为添加层级编号，为此可能会有重复的存在，因此我们使用HashSet<T>来剔除我们的重复数据，最终获取到有用数据再通过非递归遍历方法，我们便可以再次构建出树形(tree)，来转化为JSON数据。

来源：http://www.cnblogs.com/umeall/p/7660351.html?utm_source=tuicool&utm_medium=referral