搜索树，遍历C#的最简方法

Question

我需要能够搜索一个拥有任意数量子节点的树结构。树结构可能长这个样子。

                                   P
                                /  |  \
                               C   C   C     layer 1
                             / | \
                            C  C  C          layer 2
                            |
                            C                layer 3
                          / | \
                         C  C  C             layer 4

如果每个C中有任意数量的子节点，对于第一层每个起始节点都有一个双向链表是否方便？（在第一层中，非扩展节点也可能会扩展）。 我需要评估并处理每棵子树。

什么是最简单的方法？ 或者也许某种深度优先搜索/广度优先搜索更好？ 树是动态构建的。

谢谢

- Robin F

Answer 1

这个最简单的方法是使用递归。

假设你的树存储类型为 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;
        }
    }
}

- Matthew Watson