如何有效地搜索这个层次结构?

以代码为键将所有节点添加到字典中。(你可以做一次),查字典基本上是O(1)。

void FillDictionary(Dictionary<string, Node> dictionary, Node node)
{
  if (dictionary.ContainsKey(node.Code))
    return;

  dictionary.Add(node.Code, node);

  foreach (Node child in node.Children)
    FillDictionary(dictionary, child)
}  

如果您知道根,则用法如下:

var dictionary = new Dictionary<string, Node>();
FillDictionary(dictionary, rootNode);

FillDictionary()

这是我和其他人所说的全部实现。请注意,通过使用索引字典,您将使用更多的内存(仅引用节点)来换取更快的搜索。我使用事件来动态更新索引。

编辑:

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Reflection;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            // Create the root node for the tree
            MyNode rootNode = new MyNode { Code = "abc", Description = "abc node" };

            // Instantiate a new tree with the given root node.  string is the index key type, "Code" is the index property name
            var tree = new IndexedTree<MyNode, string>("Code", rootNode);

            // Add a child to the root node
            tree.Root.AddChild(new MyNode { Code = "def", Description = "def node" });

            MyNode newNode = new MyNode { Code = "foo", Description = "foo node" };

            // Add a child to the first child of root
            tree.Root.Children[0].AddChild(newNode);

            // Add a child to the previously added node
            newNode.AddChild(new MyNode { Code = "bar", Description = "bar node" });


            // Show the full tree
            Console.WriteLine("Root node tree:");
            PrintNodeTree(tree.Root, 0);

            Console.WriteLine();

            // Find the second level node
            MyNode foundNode = tree.FindNode("def");

            if (foundNode != null)
            {
                // Show the tree starting from the found node
                Console.WriteLine("Found node tree:");
                PrintNodeTree(foundNode, 0);
            }

            // Remove the last child
            foundNode = tree.FindNode("foo");
            TreeNodeBase nodeToRemove = foundNode.Children[0];
            foundNode.RemoveChild(nodeToRemove);

            // Add a child to this removed node.  The tree index is not updated.
            nodeToRemove.AddChild(new MyNode { Code = "blah", Description = "blah node" });

            Console.ReadLine();
        }

        static void PrintNodeTree(MyNode node, int level)
        {
            Console.WriteLine(new String(' ', level * 2) + "[" + node.Code + "] " + node.Description);

            foreach (MyNode child in node.Children)
            {
                // Recurse through each child
                PrintNodeTree(child, ++level);
            }
        }
    }

    public class NodeEventArgs : EventArgs
    {
        public TreeNodeBase Node { get; private set; }

        public bool Cancel { get; set; }

        public NodeEventArgs(TreeNodeBase node)
        {
            this.Node = node;
        }
    }

    /// <summary>
    /// The base node class that handles the hierarchy
    /// </summary>
    public abstract class TreeNodeBase
    {
        /// <summary>
        /// A read-only list of children so that you are forced to use the proper methods
        /// </summary>
        public ReadOnlyCollection<TreeNodeBase> Children
        {
            get { return new ReadOnlyCollection<TreeNodeBase>(this.children); }
        }

        private IList<TreeNodeBase> children;

        /// <summary>
        /// Default constructor
        /// </summary>
        public TreeNodeBase()
            : this(new List<TreeNodeBase>())
        {
        }

        /// <summary>
        /// Constructor that populates children
        /// </summary>
        /// <param name="children">A list of children</param>
        public TreeNodeBase(IList<TreeNodeBase> children)
        {
            if (children == null)
            {
                throw new ArgumentNullException("children");
            }

            this.children = children;
        }

        public event EventHandler<NodeEventArgs> ChildAdding;

        public event EventHandler<NodeEventArgs> ChildRemoving;

        protected virtual void OnChildAdding(NodeEventArgs e)
        {
            if (this.ChildAdding != null)
            {
                this.ChildAdding(this, e);
            }
        }

        protected virtual void OnChildRemoving(NodeEventArgs e)
        {
            if (this.ChildRemoving != null)
            {
                this.ChildRemoving(this, e);
            }
        }

        /// <summary>
        /// Adds a child node to the current node
        /// </summary>
        /// <param name="child">The child to add.</param>
        /// <returns>The child node, if it was added.  Useful for chaining methods.</returns>
        public TreeNodeBase AddChild(TreeNodeBase child)
        {
            NodeEventArgs eventArgs = new NodeEventArgs(child);
            this.OnChildAdding(eventArgs);

            if (eventArgs.Cancel)
            {
                return null;
            }

            this.children.Add(child);
            return child;
        }

        /// <summary>
        /// Removes the specified child in the current node
        /// </summary>
        /// <param name="child">The child to remove.</param>
        public void RemoveChild(TreeNodeBase child)
        {
            NodeEventArgs eventArgs = new NodeEventArgs(child);
            this.OnChildRemoving(eventArgs);

            if (eventArgs.Cancel)
            {
                return;
            }

            this.children.Remove(child);
        }
    }

    /// <summary>
    /// Your custom node with custom properties.  The base node class handles the tree structure.
    /// </summary>
    public class MyNode : TreeNodeBase
    {
        public string Code { get; set; }
        public string Description { get; set; }
    }

    /// <summary>
    /// The main tree class
    /// </summary>
    /// <typeparam name="TNode">The node type.</typeparam>
    /// <typeparam name="TIndexKey">The type of the index key.</typeparam>
    public class IndexedTree<TNode, TIndexKey> where TNode : TreeNodeBase, new()
    {
        public TNode Root { get; private set; }

        public Dictionary<TIndexKey, TreeNodeBase> Index { get; private set; }

        public string IndexProperty { get; private set; }

        public IndexedTree(string indexProperty, TNode rootNode)
        {
            // Make sure we have a valid indexProperty
            if (String.IsNullOrEmpty(indexProperty))
            {
                throw new ArgumentNullException("indexProperty");
            }

            Type nodeType = rootNode.GetType();
            PropertyInfo property = nodeType.GetProperty(indexProperty);

            if (property == null)
            {
                throw new ArgumentException("The [" + indexProperty + "] property does not exist in [" + nodeType.FullName + "].", "indexProperty");
            }

            // Make sure we have a valid root node
            if (rootNode == null)
            {
                throw new ArgumentNullException("rootNode");
            }

            // Set the index properties
            this.IndexProperty = indexProperty;
            this.Index = new Dictionary<TIndexKey, TreeNodeBase>();

            // Add the root node
            this.Root = rootNode;

            // Notify that we have added the root node
            this.ChildAdding(this, new NodeEventArgs(Root));
        }

        /// <summary>
        /// Find a node with the specified key value
        /// </summary>
        /// <param name="key">The node key value</param>
        /// <returns>A TNode if found, otherwise null</returns>
        public TNode FindNode(TIndexKey key)
        {
            if (Index.ContainsKey(key))
            {
                return (TNode)Index[key];
            }

            return null;
        }

        private void ChildAdding(object sender, NodeEventArgs e)
        {
            if (e.Node.Children.Count > 0)
            {
                throw new InvalidOperationException("You can only add nodes that don't have children");
                // Alternatively, you could recursively get the children, set up the added/removed events and add to the index
            }

            // Add to the index.  Add events as soon as possible to be notified when children change.
            e.Node.ChildAdding += new EventHandler<NodeEventArgs>(ChildAdding);
            e.Node.ChildRemoving += new EventHandler<NodeEventArgs>(ChildRemoving);
            Index.Add(this.GetNodeIndex(e.Node), e.Node);
        }

        private void ChildRemoving(object sender, NodeEventArgs e)
        {
            if (e.Node.Children.Count > 0)
            {
                throw new InvalidOperationException("You can only remove leaf nodes that don't have children");
                // Alternatively, you could recursively get the children, remove the events and remove from the index
            }

            // Remove from the index.  Remove events in case user code keeps reference to this node and later adds/removes children
            e.Node.ChildAdding -= new EventHandler<NodeEventArgs>(ChildAdding);
            e.Node.ChildRemoving -= new EventHandler<NodeEventArgs>(ChildRemoving);
            Index.Remove(this.GetNodeIndex(e.Node));
        }

        /// <summary>
        /// Gets the index key value for the given node
        /// </summary>
        /// <param name="node">The node</param>
        /// <returns>The index key value</returns>
        private TIndexKey GetNodeIndex(TreeNodeBase node)
        {
            TIndexKey key = (TIndexKey)node.GetType().GetProperty(this.IndexProperty).GetValue(node, null);
            if (key == null)
            {
                throw new ArgumentNullException("The node index property [" + this.IndexProperty + "] cannot be null", this.IndexProperty);
            }

            return key;
        }
    }
}

如果没有任何基于比较的代码组织,就无法阻止对树的O(n)遍历。但是,如果在读取XML文件以构建节点树的同时构建另一个数据结构(用于O(1)访问的字典或用于O(log n)访问的列表),则可以构建额外的结构以快速访问,而无需更多开销。

将它们存储在字典中,这将为您提供O(1)个查找时间。

var dict = new Dictionary<string, Node>();
dict.Add(n.Code, n);

假设 n 是有水分的 Node

var node = dict["CODEKEY"];

它将根据提供的密钥返回您的特定节点。您甚至可以使用以下方式检查节点的存在:

if (d.ContainsKey("CODEKEY"))
{
   //Do something
}

为了知道节点在原始集合中的位置,您需要向节点类添加某种指针层次结构,以便它知道上一个节点

如果可以更改节点的顺序,则可以 Binary Search Tree .

This SO answer 引用您应该能够使用的库?

Itay's suggestion 没有完全的意义。

以下是您提出的要求:

Code .

所以 代码 Node 对象转换为 Dictionary<string, Node> .

在你对Itay回答的评论中,你这样说:

如果你的意思是你不明白字典怎么会知道你的 节点 在数据结构中 ,那是因为它不是。这有关系吗?您没有在需求中声明希望知道节点在数据结构中的位置;您只指定了 . 为了做到这一点,字典只需要知道节点在内存中的位置,而不是在一些完全独立的数据结构中。

举一个简单的例子(如果我在这里侮辱了你的智慧,我很抱歉,但请容忍我,因为这至少可以为其他人澄清这一点),假设你有一个 LinkedList<int> 包含所有唯一整数的。然后在此列表上枚举并使用它构造 Dictionary<int, LinkedListNode<int>> ,其思想是希望能够根据节点的值快速找到节点。

字典需要知道在哪里吗 每个节点是?当然不仅仅是在记忆中。一旦您使用字典在O(1)中找到了基于其值的节点,您当然可以使用节点本身轻松地向前或向后遍历链接列表,而节点本身恰好知道(通过设计)包含它的链接列表。

你的层次结构也一样,只比链表复杂一点。但同样的原则也适用。

为什么不使用 SortedSet <Node> Code -容器的作用域必须使其在所有成员中都是唯一的。