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

更新時間：2017年10月13日 14:54:29 作者：umeall

這篇文章主要介紹了C#構建樹形結構數據(全部構建,查找構建)，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

摘要：

最近在做任務管理，任務可以無限派生子任務且沒有數量限制，前端采用Easyui的Treegrid樹形展示控件。

一、遇到的問題

獲取全部任務拼接樹形速度過慢(數據量大約在900條左右)且查詢速度也并不快；

二、解決方法

1、Tree轉化的JSON數據格式

a.JSON數據格式：

[
  {
    "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結構的通用性，我們可以定義一個抽象的公用實體TreeObject以保證后續(xù)涉及到的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的頂級數據(即不存在父級的任務),我們通過頂級任務依次遞歸遍歷它們的子節(jié)點。

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 = "節(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("生成任務數："+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;

    }

編寫調用遞歸方法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();
    }

啟動查看執(zhí)行結果：

發(fā)現一個問題，遞歸3s，非遞歸0s，隨后我又進行了更多的測試：

執(zhí)行時間測試

任務個數	遞歸(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:因包含的嵌套方法調用過多而導致執(zhí)行堆棧溢出時引發(fā)的異常。此類不能被繼承。

StackOverflowException 執(zhí)行堆棧溢出發(fā)生錯誤時引發(fā)，通常發(fā)生非常深度或無限遞歸。

-:沒有等到結果。

當然這個測試并不專業(yè)，但是也展示出了它的效率的確滿足了當前的需求。

4、查找構建樹形結果

原理同上述非遞歸相同，不同之處是我們通過查找的數據去構建樹形

我們通過查找獲取到圈中的任務,再通過當前節(jié)點獲取到父級節(jié)點，因為當時沒考慮到任務層級的關系，因此為添加層級編號，為此可能會有重復的存在，因此我們使用HashSet<T>來剔除我們的重復數據，最終獲取到有用數據再通過非遞歸遍歷方法，我們便可以再次構建出樹形(tree)，來轉化為JSON數據。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

.NET(C#):Emit創(chuàng)建異常處理的方法
.NET(C#):Emit創(chuàng)建異常處理的方法，需要的朋友可以參考一下
2013-04-04
C#讀寫xml文件方法總結(超詳細!)
項目中用到關于xml文件讀寫操,所以下面這篇文章主要給大家介紹了關于C#讀寫xml文件方法的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
2023-02-02
.Net?Core以windows服務方式部署
這篇文章介紹了.Net?Core以windows服務方式部署，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2022-01-01
C#中的除法運算符與VB.NET中的除法運算符
這篇文章主要介紹了C#中的除法運算符與VB.NET中的除法運算符,需要的朋友可以參考下
2014-10-10
C#實現讀取寫入Json文件
這篇文章主要介紹了C#實現讀取寫入Json文件方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-01-01
C#調用?？倒I(yè)相機SDK采集圖像并在Halcon窗口中顯示方式
這篇文章主要介紹了C#調用海康工業(yè)相機SDK采集圖像并在Halcon窗口中顯示方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-02-02
c#使用wmi查詢usb設備信息示例
這篇文章主要介紹了c#使用wmi查詢usb設備信息示例,大家參考使用吧
2014-01-01
c# 獲取網頁中指定的字符串信息的實例代碼
c# 獲取網頁中指定的字符串信息的實例代碼，需要的朋友可以參考一下
2013-04-04
c# Selenium爬取數據時防止webdriver封爬蟲的方法
這篇文章主要介紹了c# Selenium爬取數據時防止webdriver封爬蟲的方法，幫助大家更好的理解和使用c#，感興趣的朋友可以了解下
2021-01-01
C# 利用ICSharpCode.SharpZipLib實現在線壓縮和解壓縮
本文主要主要介紹了利用ICSharpCode.SharpZipLib第三方的DLL庫實現在線壓縮和解壓縮的功能，并做了相關的代碼演示。
2016-04-04