在c＃中构建一个简单，高性能的树数据结构
我需要以树型创建产品目录。
每个树节点都以ID（字符串）表示，树数据上的函数只有2：
-
getChild(string ID)，提供ID，获取子项（不需要包含子项的子项），如果ID为null，则获取所有根节点 -
getParent(string ID)，如果有，则返回父ID，如果是root，则返回null
既然树一旦决定，就不会改变，所以我认为把所有代码放在静态中会是最好的。 所以我开始尝试使用Dictionary
"id": {parent:ID, child:[id2, id3, id4....]}
由于大约1000多个目录，我发现我很快弄乱了自己，静态数据中出现了很多错误，并使最终结果可用。 此外，现在我只写了几十个，代码看起来像混乱。
请建议以高性能创建这个简单的目录树。 谢谢
只是做一个课程。
更新：
class TreeNode : IEnumerable { private readonly Dictionary _children = new Dictionary(); public readonly string ID; public TreeNode Parent { get; private set; } public TreeNode(string id) { this.ID = id; } public TreeNode GetChild(string id) { return this._children[id]; } public void Add(TreeNode item) { if (item.Parent != null) { item.Parent._children.Remove(item.ID); } item.Parent = this; this._children.Add(item.ID, item); } public IEnumerator GetEnumerator() { return this._children.Values.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } public int Count { get { return this._children.Count; } } }
静态定义的用法非常简单：
var tree = new TreeNode("Root") { new TreeNode("Category 1") { new TreeNode("Item 1"), new TreeNode("Item 2"), new TreeNode("Item 3"), }, new TreeNode("Category 2") { new TreeNode("Item 1"), new TreeNode("Item 2"), new TreeNode("Item 3"), new TreeNode("Item 4"), } };
编辑
更多function，更容易创建……
public static TreeNode BuildTree(string tree) { var lines = tree.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries); var result = new TreeNode("TreeRoot"); var list = new List { result }; foreach (var line in lines) { var trimmedLine = line.Trim(); var indent = line.Length - trimmedLine.Length; var child = new TreeNode(trimmedLine); list[indent].Add(child); if (indent + 1 < list.Count) { list[indent + 1] = child; } else { list.Add(child); } } return result; } public static string BuildString(TreeNode tree) { var sb = new StringBuilder(); BuildString(sb, tree, 0); return sb.ToString(); } private static void BuildString(StringBuilder sb, TreeNode node, int depth) { sb.AppendLine(node.ID.PadLeft(node.ID.Length + depth)); foreach (var child in node) { BuildString(sb, child, depth + 1); } }
用法：
var tree = TreeNode.BuildTree(@" Cat1 Sub1 Item1 Item2 Item3 Sub2 Item1 Item2 Cat2 Sub1 Sub2 Item1 Item2 Sub3 Item1 Cat3 Cat4");
我创建了一个可能有用的Node类 。 它很快并且具有一些额外的属性，例如：
- 祖先
- 后人
- 兄弟姐妹
- 节点的级别
- 亲
- 根
- 等等。
你可以写一个简单的二叉树，我写的是伪代码beloew：
class TreeNode { TreeNode Right; TreeNode Left; int id; //... } class BinTree { void Insert(TreeNode node) { while(true) { if(node.id > target.id) { if(target.Right != null) { target = target.Right; continue; } else { target.Right = node; break; } } else if(node.id < target.id) { if(target.Left != null) { target = target.Left; continue; } else { target.Left = node; break; } } else { throw new ArgumentException("Duplicated id"); } } } TreeNode Search(int id) { TreeNode target = root; while(target != null) { if(id > target.id) { target = target.Right; } else if(id < target.id) { target = target.Left; } else { return target; } } return null; } }
但是如果你的数据量非常大，那么AVL树可能更有效率