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

问题描述：

我有一棵如下树：

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

我正在使用称为Node的类创建此树，如下所示：

I am creating this tree using a class called Node as below:

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/ ，但是我不知道如何按顺序打印所有节点。

I wanted as a result to print out the ordered tree: 1 2 3 4 5 6 7. I am able to find the next larger element referring to this example https://www.geeksforgeeks.org/next-larger-element-n-ary-tree/ , but I can't find out how to print the all nodes in order.

已编辑：

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 类：

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

答

您需要递归 / iterator 函数遍历所有分支并获取所有节点：

You need a recursive / iterator function to iterate over all the branches and get all the nodes:

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

如果您有一棵像这样的树：

If you have a tree like:

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 节点，并通过 Data 属性订购：

Call the function, pass the root node, and OrderBy the Data property:

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 类型。

Preferably, make it an extension method for the Node type.

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

所以您可以这样称呼它：

So you can call it as follows:

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

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

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

相关推荐