无法搜索C#中的所有树节点

Question

我有一棵使用 class 节点构建的树，其中 class 的实例代表树中的一个节点。为简单起见，该节点有一个 int 类型的数据字段。

扩展方法 NodeExtensions.Next() 在树中查找下一个元素。您可以根据需要编写任意数量的辅助方法，但不要更改扩展方法的签名 NodeExtensions.Next().

我无法回到节点2再移动到子节点3，请帮我算法。

节点 class 看起来像这样：

public class Node
{
    private List<Node> _children;

    public Node(int data, params Node[] nodes)
    {
        Data = data;
        AddRange(nodes);
    }

    public Node Parent { get; set; }

    public IEnumerable<Node> Children
    {
        get
        {
            return _children != null
                ? _children
                : Enumerable.Empty<Node>();
        }
    }

    public int Data { get; private set; }

    public void Add(Node node)
    {
        Debug.Assert(node.Parent == null);

        if (_children == null)
        {
            _children = new List<Node>();
        }

        _children.Add(node);
        node.Parent = this;
    }

    public void AddRange(IEnumerable<Node> nodes)
    {
        foreach (var node in nodes)
        {
            Add(node);
        }
    }

    public override string ToString()
    {
        return Data.ToString();
    }
}

测试方法

[Test]
    public void Test()
    {
        // Test tree:
        // 
        // 1
        // +-2
        //   +-3
        //   +-4
        // +-5
        //   +-6
        //   +-7
        //
        var root = new Node(
            1,
            new Node(
                2,
                new Node(3),
                new Node(4)),
            new Node(
                5,
                new Node(6),
                new Node(7)));

        // Expected output:
        //
        // 1
        // 2
        // 3
        // 4
        // 5
        // 6
        // 7
        //
        var n = root;
        while (n != null)
        {
            Console.WriteLine(n.Data);
            n = n.Next();
        }

        // Test
        //
        n = root;
        Assert.AreEqual(1, n.Data);
        n = n.Next();
        Assert.AreEqual(2, n.Data);
        n = n.Next();
        Assert.AreEqual(3, n.Data);
        n = n.Next();
        Assert.AreEqual(4, n.Data);
        n = n.Next();
        Assert.AreEqual(5, n.Data);
        n = n.Next();
        Assert.AreEqual(6, n.Data);
        n = n.Next();
        Assert.AreEqual(7, n.Data);
        n = n.Next();
        Assert.IsNull(n);
    }

我的代码

public static Node Next(this Node node)
    {
    
        if(node != null && node.Children != null && node.Children.Count() > 0)
        {
            for(int i = 0; i < node.Children.Count(); i++)
            {
               foreach(var child in node.Children)
               {
                 child.Next();
                 return child;
               }
            }
        }
        else{
            return null;
        }
   
    }

我的代码输出
1
2
3

预期输出应该是

1
2
3
4
5
6
7

Answer 1

这有效并通过了您的测试。我假设您无法更改 Node class.

public static Node Next(this Node node)
    {
        if (node.Children.Any())
            return node.Children.First();

        var parent = node.Parent;
        while (parent != null)
        {
            var nextNode = parent.Children.FindChildAfter(node);
            if (nextNode == null)
            {
                node = parent;
                parent = parent.Parent;
            }
            else
                return nextNode;
        }

        return null;
    }

    public static Node FindChildAfter(this IEnumerable<Node> items, Node item)
    {
        bool found = false;
        foreach (var it in items)
        {
            if (found) return it;
            if (ReferenceEquals(it, item)) 
                found = true;
        }

        return null;
    }

FindChildAfter 效率低下，因为它每次都必须遍历整个集合。会有更好的方法来构建它，所以情况并非如此。

Answer 2

作为替代方法，您可以考虑让 Node 实施 IEnumerable<Node>。如果你这样做那么你只需要实现这两个方法：

public IEnumerator<Node> GetEnumerator()
{
    yield return this;
    foreach (var child in Children)
        foreach (var x in child)
            yield return x;
}

IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

现在遍历您的节点很简单了：

var data = root.Select(x => x.Data).ToArray();

这给了我一个 1, 2, 3, 4, 5, 6, 7 的数组。

无法搜索C#中的所有树节点

Unable to search all the tree nodes in C#

c#

binary-tree

depth-first-search

binary-search-tree