如何找到树中的下一个元素

Question

我有一棵如下所示的树：

/* Tree 
*            5 
*         /    \ 
*        3      1 
*       / \    / \ 
*      2   4  6   7 
*/

我正在使用名为 Node 的 class 创建这棵树，如下所示：

var root = new Node(
            5,
            new Node(
                3,
                new Node(2),
                new Node(4)),
            new Node(
                1,
                new Node(6),
                new Node(7)));

结果我想打印出有序树：1 2 3 4 5 6 7。我能够找到引用此示例的下一个更大的元素 https://www.geeksforgeeks.org/next-larger-element-n-ary-tree/ ，但我无法找到如何按顺序打印所有节点。

已编辑：

public static class Program
{
    static void Main(string[] args)
    {
        var root = new Node(
        5,
        new Node(
            3,
            new Node(2),
            new Node(4)),
        new Node(
            1,
            new Node(6),
            new Node(7)));

        var n = root;

        while (n != null)
        {
            Console.WriteLine(n.Data);
            n = n.NextNode();
        }
    }

    public static Node NextNode(this Node node)
    {
        var newNode = NextLargerElement(node, node.Data);

        return newNode;
    }

    public static Node res;
    public static Node NextLargerElementUtil(Node root, int x) 
    {
        if (root == null)
            return null;

        if (root.Data > x)
            if ((res == null || (res).Data > root.Data))
                res = root;

        foreach (var children in root.Children)
        {
            NextLargerElementUtil(children, x);
        }

        return res;
    }

    static Node NextLargerElement(Node root, int x)
    {
        res = null;

        NextLargerElementUtil(root, x);

        return res;
    }
}

和 Node 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();
    }
}

Answer 1

您需要一个 recursive / iterator 函数来遍历所有分支并获取所有节点：

public IEnumerable<Node> GetAllNodes(Node parent)               
{
    IEnumerable<Node> GetAllNodes(IEnumerable<Node> children)
    {
        foreach(var child in children)
        {
            yield return child;
            foreach(var c in GetAllNodes(child.Children))
                yield return c;
        }
    }

    yield return parent;

    foreach(var child in GetAllNodes(parent.Children))
        yield return child;
}

如果你有这样一棵树：

var root = new Node(5,
    new Node(3, new Node(11), new Node(12),
    new Node(2),
    new Node(4), new Node(13)),
    new Node(1, new Node(14), new Node(15),
    new Node(6, new Node(16), new Node(17)),
    new Node(7, new Node(8), new Node(9))), new Node(10));

调用函数，传递root节点，OrderBy Data 属性:

var q = GetAllNodes(root).OrderBy(x => x.Data).Select(x => x.Data);

Console.WriteLine(string.Join(", ", q));

输出为：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17

最好将其设为 Node 类型的 extension method。

static class Extensions
{
    public static IEnumerable<Node> GetAllNodes(this Node parent)
    {
        IEnumerable<Node> GetAllNodes(IEnumerable<Node> children)
        {
            foreach (var child in children)
            {
                yield return child;
                foreach (var c in GetAllNodes(child.Children))
                    yield return c;
            }
        }

        yield return parent;

        foreach (var child in GetAllNodes(parent.Children))
            yield return child;
    }
}

所以你可以这样调用它：

var q = root.GetAllNodes().OrderBy(x => x.Data).Select(x => x.Data);

Console.WriteLine(string.Join(", ", q));

如何找到树中的下一个元素

How to find the next element in the tree

.net

c#

tree

console-application

.net-core