您好,登錄后才能下訂單哦!
這篇文章給大家介紹C#中怎么構(gòu)建一個樹形結(jié)構(gòu)數(shù)據(jù),內(nèi)容非常詳細,感興趣的小伙伴們可以參考借鑒,希望對大家能有所幫助。
一、遇到的問題
獲取全部任務(wù)拼接樹形速度過慢(數(shù)據(jù)量大約在900條左右)且查詢速度也并不快;
二、解決方法
1、Tree轉(zhuǎn)化的JSON數(shù)據(jù)格式
a.JSON數(shù)據(jù)格式:
[ { "children":[ { "children":[ ], "username":"username2", "password":"password2", "id":"2", "pId":"1", "name":"節(jié)點2" }, { "children":[ ], "username":"username2", "password":"password2", "id":"A2", "pId":"1", "name":"節(jié)點2" } ], "username":"username1", "password":"password1", "id":"1", "pId":"0", "name":"節(jié)點1" }, { "children":[ ], "username":"username1", "password":"password1", "id":"A1", "pId":"0", "name":"節(jié)點1" } ]
b.定義實體必要字段
為了Tree結(jié)構(gòu)的通用性,我們可以定義一個抽象的公用實體TreeObject以保證后續(xù)涉及到的List<T>轉(zhuǎn)化樹形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、遞歸遍歷
獲取全部任務(wù)并轉(zhuǎn)化為樹形
獲取全部任務(wù)轉(zhuǎn)化為樹形是比較簡單的,我們首先獲取到pId=0的頂級數(shù)據(jù)(即不存在父級的任務(wù)),我們通過頂級任務(wù)依次遞歸遍歷它們的子節(jié)點。
b.我們暫時id以1開始則pId=0的都為頂級任務(wù)
我們首先寫一段生成數(shù)據(jù)的方法:
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 = "節(jié)點" + i, username = "username" + i, password = "password" + i }); datas.Add(new TreeModel { id = "A" + i.ToString(), pId = (i - 1).ToString(), name = "節(jié)點" + 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("生成任務(wù)數(shù):"+count+"個"); Console.Read(); }
我們再寫一個遞歸獲取子節(jié)點的遞歸方法:
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; }
編寫調(diào)用遞歸方法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");//獲取頂級任務(wù) foreach (var item in mds_0) { item.children = GetChildrens(item); } sw.Stop(); Console.WriteLine("----------遞歸遍歷用時:" + sw.ElapsedMilliseconds + "----------線程名稱:"+t1.Name+",線程ID:"+t1.ManagedThreadId); #endregion }
編寫main函數(shù)啟動測試:
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("生成任務(wù)數(shù):"+count+"個"); models = GetData(count); t1 = new Thread(Recursion); t1.Name = "遞歸遍歷"; t1.Start(); Console.Read(); }
輸出結(jié)果:
遞歸遍歷至此結(jié)束。
3、非遞歸遍歷
非遞歸遍歷在操作中不需要遞歸方法的參與即可實現(xiàn)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函數(shù):
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("生成任務(wù)數(shù):"+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(); }
啟動查看執(zhí)行結(jié)果:
發(fā)現(xiàn)一個問題,遞歸3s,非遞歸0s,隨后我又進行了更多的測試:
執(zhí)行時間測試
任務(wù)個數(shù) | 遞歸(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 |
StackOverflowException:因包含的嵌套方法調(diào)用過多而導致執(zhí)行堆棧溢出時引發(fā)的異常。 此類不能被繼承。
StackOverflowException 執(zhí)行堆棧溢出發(fā)生錯誤時引發(fā),通常發(fā)生非常深度或無限遞歸。
-:沒有等到結(jié)果。
當然這個測試并不專業(yè),但是也展示出了它的效率的確滿足了當前的需求。
4、查找構(gòu)建樹形結(jié)果
原理同上述非遞歸相同,不同之處是我們通過查找的數(shù)據(jù)去構(gòu)建樹形
關(guān)于C#中怎么構(gòu)建一個樹形結(jié)構(gòu)數(shù)據(jù)就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。