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

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

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

-:没有等到结果。

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

4、查找构建树形结果

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

    

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-10-12

C#数据结构与算法揭秘一

这里,我们 来说一说C#的数据结构了. ①什么是数据结构.数据结构,字面意思就是研究数据的方法,就是研究数据如何在程序中组织的一种方法.数据结构就是相互之间存在一种或多种特定关系的数据元素的集合. 程序界有一点很经典的话,程序设计=数据结构+算法.用源代码来体现,数据结构,就是编程.他有哪些具体的关系了, (1) 集合(Set):如图 1.1(a)所示,该结构中的数据元素除了存在"同属于一个集合"的关系外,不存在任何其它关系. 集合与数学的集合类似,有无序性,唯一性,确定性. (2)

C#数据结构与算法揭秘四 双向链表

首先,明白什么是双向链表.所谓双向链表是如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List).双向链表的结点结构示意图如图所示. 双向链表结点的定义与单链表的结点的定义很相似, ,只是双向链表多了一个字段 prev.其实,双向链表更像是一根链条一样,你连我,我连你,不清楚,请看图. 双向链表结点类的实现如下所示

C#数据结构之循环链表的实例代码

复制代码 代码如下: public class Node    {        public object Element;        public Node Link; public Node()        {            Element = null;            Link = null;        } public Node(object theElement)        {            Element = theElement;      

C#数据结构揭秘一

这里,我们 来说一说C#的数据结构了. ①什么是数据结构.数据结构,字面意思就是研究数据的方法,就是研究数据如何在程序中组织的一种方法.数据结构就是相互之间存在一种或多种特定关系的数据元素的集合. 程序界有一点很经典的话,程序设计=数据结构+算法.用源代码来体现,数据结构,就是编程.他有哪些具体的关系了, (1) 集合(Set):如图 1.1(a)所示,该结构中的数据元素除了存在"同属于一个集合"的关系外,不存在任何其它关系. 集合与数学的集合类似,有无序性,唯一性,确定性. (2)

C#常用数据结构和算法总结

1.数据 数据(Data)是外部世界信息的载体, 是能够被计算机识别,加工,存储的.在现实生活中也就是我们的产品原材料. 计算机中的数据包括数值数据,图片,影音资料等. 2. 数据元素和数据项 数据元素(Data Element)是数据的基本单位,在计算机处理的过程中通常是作为一个整体来作为处理的. 数据项(Data Item):一个数据元素通常由一个或多个数据项组成. 比如数据库表:(Student),它有Id,Name,Sex,Age,Address等字段,而这张表又有多行数据.我们通常将这

C#数据结构与算法揭秘三 链表

上文我们讨论了一种最简单的线性结构--顺序表,这节我们要讨论另一种线性结构--链表. 什么是链表了,不要求逻辑上相邻的数据元素在物理存储位置上也相邻存储的线性结构称之为链表.举个现实中的例子吧,假如一个公司召开了视频会议的吧,能在北京总公司人看到上海分公司的人,他们就好比是逻辑上相邻的数据元素,而物理上不相连.这样就好比是个链表. 链表分为①单链表,②单向循环链表,③双向链表,④双向循环链表. 介绍各种各样链表之前,我们要明白这样一个概念.什么是结点.在存储数据元素时,除了存储数据元素本身的信息

C#数据结构与算法揭秘五 栈和队列

这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

C#数据结构之单链表(LinkList)实例详解

本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data

javascript数据结构之双链表插入排序实例详解

本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

C++ 单链表的基本操作(详解)

链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&

jQuery表单插件ajaxForm实例详解

前端时间写项目用到了ajaxForm这个插件,可以用它提交表单和上传图片,听起来和正常的form表单提交没什么区别,只不过是ajax提交,无需刷新页面,如此可以增加用户体验度. 引入两个文件,PS:必须 <script type="text/javascript" src="http://img9.tongzhuo100.com/js/jquery-1.7.2.min.js"></script> <script type="t

java 设计模式之单例的实例详解

java 设计模式之单例的实例详解 设计模式思想 什么是设计模式:我作为初学者,今天第一次正式学习设计模式,我觉得对与理解什么是设计模式很重要,那么什么是设计模式呢? 设计模式:解决问题的一种行之有效的思想. 设计模式:用于解决特定环境下.重复出现的特定问题的解决方案 我的理解是前人在软件设计的时候碰到了一类问题,他们总结出了一套行之有效,并且经过验证的解决方案. 设计模式的优点: 1.设计模式都是一些相对优秀的解决方案,很多问题都是典型的.有代表性的问题,学习设计模式,我们就不用自己从头来解决

C语言数据结构之图的遍历实例详解

C语言数据结构之图的遍历实例详解 输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st

JAVA 静态的单例的实例详解

JAVA  静态的单例的实例详解 实现代码: public class Printer { private Printer(){ } public static Printer newInstance(){ return CreatePrinter.mPrinter; } private static class CreatePrinter{ private final static Printer mPrinter = new Printer(); } } 因为静态的单例对象没有作为类的成员变

Vuejs 单文件组件实例详解

在之前的实例中,我们都是通过 Vue.component 或者 components 属性的方式来定义组件,这种方式在很多中小规模的项目中还好,但在复杂的项目中,下面这些缺点就非常明显了: 字符串模板:缺乏高亮,书写麻烦,特别是 HTML 多行的时候,虽然可以将模板写在 html 文件中,但是侵入性太强,不利于组件解耦分离. 不支持CSS:意味着当 HTML 和 JavaScript 组件化时,CSS明显被遗漏了 没有构建步骤:限制只能使用 HTML 和 ES5 JavaScript,而不能使用

C语言单链表实现方法详解

本文实例讲述了C语言单链表实现方法.分享给大家供大家参考,具体如下: slist.h #ifndef __SLIST_H__ #define __SLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> typedef int ElemType; typedef struct Node { //定义单链表中的结点信息 ElemType data; //结点的数据域 struct Node *next

JS中的算法与数据结构之链表(Linked-list)实例详解

本文实例讲述了JS中的算法与数据结构之链表(Linked-list).分享给大家供大家参考,具体如下: 链表(Linked-list) 前面我们讨论了如何使用栈.队列进行存数数据,他们其实都是列表的一种,底层存储的数据的数据结构都是数组. 但是数组不总是最佳的数据结构,因为,在很多编程语言中,数组的长度都是固定的,如果数组已被数据填满,再要加入新的元素是非常困难的.而且,对于数组的删除和添加操作,通常需要将数组中的其他元素向前或者向后平移,这些操作也是十分繁琐的. 然而,JS中数组却不存在上述问