c# - 搜索树，最简单的c#遍历方法

Question

我需要能够搜索具有任意多个 child 的树。它可能看起来像这样。

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

每个 C 中有任意多个 child 。为第 1 层中的每个起始节点设置一个双链表是否方便？ (在第 1 层中，非扩展节点当然也可能扩展)。我需要评估和处理每个子树。

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

谢谢

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;
        }
    }
}