搜索树，遍历c＃的最简单方法-Java 学习之路

我需要能够搜索任意多个孩子的树 . 它可能看起来像这样 .

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

在每个C中有任意多个子节点 . 在第1层中为每个起始节点设置双链表是否方便？（在第1层中，非扩展节点也可能会扩展） . 我需要评估并使用每个子树 .

什么是最简单的方法？或者也许某种深度优先搜索/广度优先搜索更好？树是在飞行中构建的 .

谢谢

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

回复于 2024-04-25T15:48:51+08:00

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

1 回答

相关问题