代码之家 › 专栏 › 技术社区 › logicnp

如何使用泛型编写真正的通用树

generics .net c#

logicnp · 技术社区 · 14 年前

假设我有一个节点类,如下所示:

    class Node<T>
    {
        T data;
        List<Node<T>> children;
        internal Node(T data)
        {
            this.data = data;
        }

        List<Node<T>> Children
        {
            get
            {
                if (children == null)
                    children = new List<Node<T>>(1);

                return children;
            }
        }

        internal IEnumerable<Node<T>> GetChildren()
        {
            return children;
        }

        internal bool HasChildren
        {
            get
            {
                return children != null;
            }
        }

        internal T Data
        {
            get
            {
                return data;
            }
        }



        internal void AddChild(Node<T> child)
        {
            this.Children.Add(child);
        }

        internal void AddChild(T child)
        {
            this.Children.Add(new Node<T>(child));
        }

    }

问题是树的每个节点都局限于一种类型。但是,在某些情况下,根节点是一种类型,而另一种类型的子节点是第三种类型的子节点(示例文档-->段落-->行-->单词)。

如何为此类情况定义通用树?

4 回复 | 直到 14 年前

GraemeF 14 年前

如果需要严格的类型层次结构,可以这样声明:

class Node<T, TChild> {...}

Node<Document, Node<Paragraph, Node<Line, Word>>>

我没有说它会很漂亮。:)

Eric Lippert 14 年前

如何为此类情况定义通用树?

我一开始不会这么做。如果我想做的模型是:

我有一份文件清单
文件有一个段落列表
一段有一个单词列表

那么,为什么需要通用节点呢?制作一个具有 List<Word> ,生成具有 List<Paragraph> 然后做一个 List<Document> 你就完了。为什么需要人为地强制一个通用的树结构?这对你有什么好处?

JeffreyABecker 14 年前

让所有子对象实现特定的,例如IDocumentPart,然后声明节点

BillW 14 年前

我不愿意提供所附的代码示例,我觉得我对stackoverflow的“规范”还没有很强的理解,就发布代码而言,这可能是“推测性的”,而且,我觉得这种特殊的嬉戏是某种“突变物种”从“Moreau博士岛”的实验室中逃逸出来的:而且,我确实认为Answe上面是埃里克·利珀特的R。

因此,请将下面的“一粒盐”作为“探测.NET继承”的实验(使用框架3.5工具)。我写这篇文章的目的(几个月前)是为了实验一个抽象节点类基础结构,它实现了“自身”的内部列表& lt;& gt;然后实现从抽象类继承的强类型类…在此基础上,构建了一个通用的树型数据结构。

事实上,当我测试这个的时候,我很惊讶,它起作用了!:)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// experimental code : tested to a limited extent
// use only for educational purposes

namespace complexTree
{
    // foundation abstract class template
    public abstract class idioNode
    {
        // a collection of "itself" !
        public List<idioNode> Nodes { private set; get; }

        public idioNode Parent { get; set; }

        public idioNode()
        {
            Nodes = new List<idioNode>();
        }

        public void Add(idioNode theNode)
        {
            Nodes.Add(theNode);
            theNode.Parent = this;
        }
    }

    // strongly typed Node of type String
    public class idioString : idioNode
    {
        public string Value { get; set; }

        public idioString(string strValue)
        {
            Value = strValue;
        }
    }

    // strongly typed Node of type Int
    public class idioInt : idioNode
    {
        public int Value { get; set; }

        public idioInt(int intValue)
        {
            Value = intValue;
        }
    }

    // strongly type Node of a complex type
    // note : this is just a "made-up" test case
    // designed to "stress" this experiment
    // it certainly doesn't model any "real world"
    // use case
    public class idioComplex : idioNode
    {
        public Dictionary<idioString, idioInt> Value { get; set; }

        public idioComplex(idioInt theInt, idioString theString)
        {
            Value = new Dictionary<idioString, idioInt>();
            Value.Add(theString, theInt);
        }

        public void Add(idioInt theInt, idioString theString)
        {
            Value.Add(theString, theInt);
            theInt.Parent = this;
            theString.Parent = this;
        }
    }

    // special case the Tree's root nodes
    // no particular reason for doing this
    public class idioTreeRootNodes : List<idioNode>
    {
        public new void Add(idioNode theNode)
        {
            base.Add(theNode);
            theNode.Parent = null;
        }
    }

    // the Tree object
    public class idioTree
    {
        public idioTreeRootNodes Nodes { get; set; }

        public idioTree()
        {
            Nodes = new idioTreeRootNodes();
        }
    }
}

因此,对于测试:(从WinForm上的某个事件处理程序调用此代码):

    // make a new idioTree
    idioTree testIdioTree = new idioTree();

    // make a new idioNode of type String
    idioString testIdioString = new idioString("a string");

    // add the Node to the Tree
    testIdioTree.Nodes.Add(testIdioString);

    // make a new idioNode of type Int
    idioInt testIdioInt = new idioInt(99);

    // add to Tree
    testIdioTree.Nodes.Add(testIdioInt);

    // make another idioNode of type String
    idioString testIdioString2 = new idioString("another string");

    // add the new Node to the child Node collection of the Int type Node
    testIdioInt.Nodes.Add(testIdioString2);

    // validate inheritance can be verified at run-time
    if (testIdioInt.Nodes[0] is idioString) MessageBox.Show("it's a string, idiot");

    if (!(testIdioInt.Nodes[0] is idioInt)) MessageBox.Show("it's not an int, idiot");

    // make a new "complex" idioNode
    // creating a Key<>Value pair of the required types of idioNodes
    idioComplex complexIdio = new idioComplex(new idioInt(88), new idioString("weirder"));

    // add a child Node to the complex idioNode
    complexIdio.Add(new idioInt(77), new idioString("too weird"));

    // make another idioNode of type Int
    idioInt idioInt2 = new idioInt(33);

    // add the complex idioNode to the child Node collection of the new Int type idioNode
    idioInt2.Nodes.Add(complexIdio);

    // add the new Int type Node to the Tree
    testIdioTree.Nodes.Add(idioInt2);

    // validate you can verify the type of idioComplex at run-time
    MessageBox.Show(" tree/2/0 is complex = " + (testIdioTree.Nodes[2].Nodes[0] is idioComplex).ToString());

如果这段代码的“气味”和泰国的水果一样难闻,我们称之为“榴莲”:好吧,就这样吧:)在这个实验中,一个明显的可能的“奇怪之处”是你可以有参考资料。 到多个位置的同一节点 同时在树上。