这个最简单的方法是使用递归。
假设你的树存储类型为 T 的项目,并且该类型实现了
IEquatable<T>
。
首先,让我们编写一个非常基本的树类:
public sealed class Node<T>
{
public Node(T value) { Value = value; }
public T Value { get; }
public IEnumerable<Node<T>> Children => _children;
public void Add(Node<T> child)
{
_children.Add(child);
}
readonly List<Node<T>> _children = new List<Node<T>>();
}
现在我们可以很简单地使用递归编写一个搜索该树的方法。如果找到了指定值的第一个节点,它将返回该节点,否则返回null。
public static Node<T> Find<T>(Node<T> root, T target) where T: IEquatable<T>
{
if (root.Value != null && root.Value.Equals(target))
return root;
foreach (var child in root.Children)
{
var found = Find(child, target);
if (found != null)
return found;
}
return null;
}
很容易将其调整为返回所有与目标匹配的节点:
public static IEnumerable<Node<T>> FindAll<T>(Node<T> root, T target) where T : IEquatable<T>
{
if (root.Value != null && root.Value.Equals(target))
yield return root;
foreach (var child in root.Children)
{
var found = FindAll(child, target);
foreach (var item in found)
yield return item;
}
}
为了演示目的,这里有一个可编译的控制台应用程序。它包括一个makeTree()
方法,我正在使用它来创建深度为4的树,每个节点都有5个子节点。
然后它使用Find<T>(Node<T> root, T target)
递归搜索树以查找指定的目标值。其中一个会成功,另一个会失败:
using System;
using System.Collections.Generic;
namespace Demo
{
public sealed class Node<T>
{
public Node(T value) { Value = value; }
public T Value { get; }
public IEnumerable<Node<T>> Children => _children;
public void Add(Node<T> child)
{
_children.Add(child);
}
readonly List<Node<T>> _children = new List<Node<T>>();
}
class Program
{
static void Main()
{
var root = makeTree(1, 1, 4, 5);
lookFor(root, "3.4");
lookFor(root, "6.3");
}
static void lookFor<T>(Node<T> root, T target) where T: IEquatable<T>
{
var found = Find(root, target);
Console.WriteLine(found != null ? $"Found {target}" : $"Did not find {target}");
}
public static Node<T> Find<T>(Node<T> root, T target) where T: IEquatable<T>
{
if (root.Value != null && root.Value.Equals(target))
return root;
foreach (var child in root.Children)
{
var found = Find(child, target);
if (found != null)
return found;
}
return null;
}
static Node<string> makeTree(int id1, int id2, int depth, int nChildren)
{
var root = new Node<string>($"{id1}.{id2}");
if (depth == 0)
return root;
for (int i = 0; i < nChildren; ++i)
root.Add(makeTree(id1+1, i+1, depth-1, nChildren));
return root;
}
}
}