C#非递归列表转树形结构的实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

说道树结构，很容易想到以下的数据结构

    class Node
    {
        public string ID { get; set; }
        public string ParentID { get; set; }
        public List<Node> Children { get; set; }
    }

View Code

一般的数据都是从数据库中读取，将数据转换为对应的实体主要有一下几种方式：
全部读取，直接转换为对应的树或者部分读取，每次点击节点的的时候再加载下级数据。

本文不讨论部分读取的情况，主要涉及的是全部读取，转为树的做法。

网上最常见的方式就是递归，思路是找出所有第一层节点，然后层层遍历，类似下面的代码

        public static List<Node> GetTree(List<Node> nodes)
        {
            var list = nodes.FindAll(a => a.ParentID == "0");
            foreach (var node in list)
            {
                GetTree(node, nodes);
            }
            return list;
        }


        public static void GetTree(Node paretnNode, List<Node> nodes)
        {
            foreach (var node in nodes)
            {
                if (node.ParentID == paretnNode.ID)
                {
                    GetTree(node, nodes);
                    paretnNode.Children.Add(node);
                }
            }
        }

View Code

写递归，总觉得好麻烦，而其需要两个方法，有没有非递归的形式？
由树的非递归遍历使用队列想到，可以用类似的方法实现，代码如下

        public static List<Node> GetTree(List<Node> list, Func<Node, bool> IsRoot)
        {
            var _list = new List<Node>(list);//复制 不修改原始数据
            for (int i = _list.Count() - 1; i > -1; i--)//不能使用foreach 删除或者添加元素。顺序遍历，删除元素之后，需要对当前索引执行--操作。逆序删除节点不需要特殊处理           
            {
                Node node = _list[i];
                if (!IsRoot(node))//顶级节点
                {
                    Node pNode = _list.FirstOrDefault(a => a.ID == node.ParentID);//找到父节点
                    if (pNode != null)
                    {
                        pNode.Children.Add(node);//添加节点
                    }
                    _list.RemoveAt(i);//无论是否找到 删除，剩下的全部为顶级节点
                }
            }
            return _list;
        }

View Code

主要思路就是每次遍历时，判断是否为顶级节点，如果不是，找到父节点，添加到父节点的子集中，删除该元素。
到遍历完成时，剩下的全部都是顶级元素，自然就是需要的树结构。

上面的Node类只是最基本的树状结构，实际使用当中，节点还有很多其他的属性，马上想到的时候通过继承Node类来实现通用。

    public class MyTreeNode : Node
    {
        public string Name { get; set; }
    }

            TreeNode.GetTree(new List<MyTreeNode>()
            {
                 new MyTreeNode { ID = "1", ParentID = "0", Name = "节点1" },
                 new MyTreeNode { ID = "2", ParentID = "0", Name = "节点2" },
                 new MyTreeNode { ID = "3", ParentID = "1", Name = "节点3" },
                 new MyTreeNode { ID = "4", ParentID = "1", Name = "节点4" },
                 new MyTreeNode { ID = "5", ParentID = "2", Name = "节点5" },
                 new MyTreeNode { ID = "6", ParentID = "1", Name = "节点6" },
                 new MyTreeNode { ID = "7", ParentID = "5", Name = "节点7" },
                 new MyTreeNode { ID = "8", ParentID = "7", Name = "节点8" },
                 new MyTreeNode { ID = "9", ParentID = "20", Name = "节点9" }
            }, a => a.ParentID == "0");

View Code

编译报错：错误 2 参数 1: 无法从“System.Collections.Generic.List<test.MyTreeNode>”转换为“System.Collections.Generic.List<test.Node>”

纳尼？MyTreeNode明明继承于Node，List<MyTreeNode>竟然不能转为List<Node>？
事实就是这么残酷，我们将上面的GetTree方法参数 list 从List<Node>改为IEnumerable<Node> ，编译就能通过了。
此处涉及到协变和逆变，具体不展开，请查阅相关资料。

由于基类的GetTree方法返回的是List<Node>，子类调用方法之后，需要再转换，最简单的就是在foreach中

            foreach (var item in _list)
            {
                Console.WriteLine(item.Name);//error
            }
            foreach (MyTreeNode item in _list)
            {
                Console.WriteLine(item.Name);
            }

View Code

在第一个foreah中，item的编译类型是Node，所以不能使用Name属性，在第二个foreach中，我们指定了遍历时的类型，代码等效于

           
            foreach (var item in _list)
            {
                MyTreeNode newitem = (MyTreeNode)item;
                Console.WriteLine(newitem.Name);
            }

View Code

大功告成。本文到此告一段落。

----------------------------------------苦逼的分割线--------------------------------------------

如果使用的是.net4.0及以上版本，就不需要再往下看了，可是苦逼的我用的是.net3.5，不能使用协变。
难道传给GetTree方法中的参数还需要再转型一遍？这样的代码，实在是缺乏美感。有木有其他的方法？

最近主要在学js，很多框架都有warp实现，马上想到通过给Node类外面包装一层

    public class Wrap
    {
        public string ID { get; set; }
        public string ParentID { get; set; }
        public List<Wrap> Children { get; set; }

        public Node Target { get; set; }

        public Wrap(Node node)
        {
            this.Target = node;
            this.ID = node.ID;
            this.ParentID = node.ParentID;
            this.Children = new List<Wrap>();
        }

        public static List<Wrap> GetTree(IEnumerable<Wrap> list, Func<Wrap, bool> IsRoot)
        {
            var _list = new List<Wrap>(list);
            for (int i = _list.Count() - 1; i > -1; i--)
            {
                Wrap node = _list[i];
                if (!IsRoot(node))
                {
                    Wrap pNode = _list.FirstOrDefault(a => a.ID == node.ParentID);
                    if (pNode != null)
                    {
                        pNode.Children.Add(node);
                    }
                    _list.RemoveAt(i);
                }
            }
            return _list;
        }
    }

View Code

用起来还是不爽，List<Warp>遍历解包得到Node，还要转型为实际类型，感觉更麻烦了！
将Node改为泛型T，试试看

    public class Wrap<T> where T : Node
    {
        public string ID { get; set; }
        public string ParentID { get; set; }
        public List<Wrap<T>> Children { get; set; }

        public T Target { get; set; }

        public Wrap(T node)
        {
            this.Target = node;
            this.ID = node.ID;
            this.ParentID = node.ParentID;
            this.Children = new List<Wrap>();
        }

        public static List<Wrap<T>> GetTree(IEnumerable<Wrap<T>> list, Func<Wrap<T>, bool> IsRoot)
        {
            var _list = new List<Wrap<T>>(list);
            for (int i = _list.Count() - 1; i > -1; i--)
            {
                Wrap<T> node = _list[i];
                if (!IsRoot(node))
                {
                    Wrap<T> pNode = _list.FirstOrDefault(a => a.ID == node.ParentID);
                    if (pNode != null)
                    {
                        pNode.Children.Add(node);
                    }
                    _list.RemoveAt(i);
                }
            }
            return _list;
        }
    }

View Code

可喜可贺，现在只需要遍历解包就能得到正确的列表了，能不能更近一步？
可以：这个时候，该重载运算符这个大杀器出场了

        public static List<Wrap<T>> GetTree(IEnumerable<T> list, Func<Wrap<T>, bool> IsRoot)
        {
            var _list = new List<Wrap<T>>(list.Count());//手动copy
            foreach (T t in list)
            {
                _list.Add(t);
            }
            for (int i = _list.Count() - 1; i > -1; i--)
            {
                Wrap<T> node = _list[i];
                if (!IsRoot(node))
                {
                    Wrap<T> pNode = _list.FirstOrDefault(a => a.ID == node.ParentID);
                    if (pNode != null)
                    {
                        pNode.Children.Add(node);
                    }
                    _list.RemoveAt(i);
                }
            }
            return _list;
        }

        public static implicit operator T(Wrap<T> warp)
        {
            return warp.Target;
        }

        public static implicit operator Wrap<T>(T t)
        {
            return new Wrap<T>(t);
        }

View Code

重载之后，使用起来和上面的那个版本基本一致。
仔细观察 Wrap的结构，可以发现和Node类的属性一摸一样，可以直接令Wrap继承于Node，代码职责是否清晰，就仁者见仁智者见智了。

其实这些都是扯淡，老老实实用上面的版本。。。。

--------------------------------最后的分割线------------------------------------

上面的代码，其中缺了一点，就是 Children中的排序，一般来说，树的每个节点都是有对应的顺序的。
（其实是因为倒序删除导致了顺序不对-_-，可以改为顺序删除）
补充如下：

                    …………
                    if (pNode != null)
                    {
                        pNode.Children.Add(node);//添加节点
                        if (NeedOrder)
                        {
                            pNode.Children = pNode.Children.OrderBy(a => a.Sequence).ToList();
                        }
                    }
                    …………

View Code

总结：本文主要涉及到的知识点：linq，递归，泛型，协变，类型转换，操作符重载
实质是用双重循环（不包括排序）来替代递归，具体效率嘛，呵呵你懂的，在实际生产环境谨慎使用