C#構建樹形結構數據(全部構建,查找構建)

2019-10-29 21:08:42

字體：大中小

來源：轉載

供稿：網友

摘要：

最近在做任務管理，任務可以無限派生子任務且沒有數量限制，前端采用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的頂級數據(即不存在父級的任務),我們通過頂級任務依次遞歸遍歷它們的子節點。

C#,查找樹形結構數據,C#構建樹形結構數據

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();    }

輸出結果：

C#,查找樹形結構數據,C#構建樹形結構數據

遞歸遍歷至此結束。

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();    }

啟動查看執行結果：

C#,查找樹形結構數據,C#構建樹形結構數據

發現一個問題，遞歸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