如何找到树中的下一个元素 [英] How to find the next element in the tree

问题描述

我有一棵树，如下所示:

I have a tree like below:

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

如果你有一棵树:

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节点，OrderByData属性:

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

最好将其设为 扩展方法.

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

这篇关于如何找到树中的下一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！