主页 / 问题 / 1159107
Accepted
polsok
Asked:2020-07-30 18:58:33 +0000 UTC2020-07-30 18:58:33 +0000 UTC

创建树

  • 772

输入是一个列表，例如：

List<string> path = new List<string>() { "первый", "второй"});

此列表的元素是嵌套节点。例如，在这种情况下，意味着需要在创建第二个节点的根节点中创建第一个节点。我写了代码，但是当使用递归方法每次在另一个节点中添加一个节点时，由于某种原因，主根节点没有变化。这是有这个问题的代码和一个例子。请告诉我如何解决它。

class Program
{
    private static Node rootNode;
    static void Main(string[] args)
    {
        rootNode = new Node("root");
        List<string> path;
        
        AddNode(rootNode, path = new List<string>() { "первый", "второй"});
        AddNode(rootNode, path = new List<string>() { "второй" });
        AddNode(rootNode, path = new List<string>() { "первый","1" });
        AddNode(rootNode, path = new List<string>() { "третий","1" });
        AddNode(rootNode, path = new List<string>() { "четвертый","1" });
        AddNode(rootNode, path = new List<string>() { "первый" });
        AddNode(rootNode, path = new List<string>() { "первый" });
    }

    static void AddNode(Node node, List<string> path)
    {
        Node childNode;

        if (node.ChildList.Count == 0)
        {
            node.ChildList.Add( new Node(path[0]));
            if (path.Count > 1)
            {
                List<string> path1 = path.GetRange(1, path.Count-1);
                AddNode(new Node(path[0]), path1);
            }
        }
        else
        {
            bool True = false;
            for (int i = 0; i < node.ChildList.Count; i++)
                if (node.ChildList[i].Name == path[0])
                {
                    True = true;
                    if (path.Count > 1)
                    {
                        List<string> path1 = path.GetRange(1, path.Count-1);
                        AddNode(new Node(path[0]), path1);
                    }
                }

            if (!True)
            {
                node.ChildList.Add(childNode = new Node(path[0]));
                if (path.Count > 1)
                {
                    List<string> path1 = path.GetRange(1, path.Count-1);
                    AddNode(new Node(path[0]), path1);
                }
            }
        }
    }

    static Node searchNode(int number)
    {
        return null;
    }
}

class Node
{
    private static int number = 0;
    public Node(string name)
    {
        Number = number;
        Name = name;
        ChildList = new List<Node>();
        number++;
    }
    public int Number { get; set; }
    public string Name { get; set; }
    public List<Node> ChildList { get; set; }
}
c#

1 个回答

  1. Best Answer

    这是这一行：

     AddNode(new Node(path[0]), path1);

    创建一个全新的Node，它不在任何树中，然后尝试添加path1。自然，新元素与根元素没有任何联系。

    相反，您需要将已创建的对象传递给方法Node。新创建的树节点，或者在搜索中找到的树节点。

    关于风格的几点说明：

    • 检查是否缺少子元素 ( if (node.ChildList.Count == 0)) 是多余的。如果没有子节点，那么在搜索过程中就根本找不到它们。可以删除整个线程。
    • 永远不要命名一个布尔变量True，它只是令人困惑。给它一个有意义的名字，比如isNodeFound.

    让我们尝试对代码进行更改（我警告你，我没有测试它）：

    Node childNode;
bool isNodeFound = false;
for (int i = 0; i < node.ChildList.Count; i++)
    if (node.ChildList[i].Name == path[0])
    {
        isNodeFound = true;
        if (path.Count > 1)
        {
             //получаем найденный узел
             childNode = node.ChildList[i];
             List<string> path1 = path.GetRange(1, path.Count-1);
             //передаем его в метод
             AddNode(childNode, path1);
        }
        //узел уже нашли, выходим из цикла
        break;
    }
if (!isNodeFound)
{
    childNode = new Node(path[0]);
    node.ChildList.Add(childNode);
    if (path.Count > 1)
    {
        List<string> path1 = path.GetRange(1, path.Count-1);
        //передаем сюда childNode
        AddNode(childNode, path1);
    }
}

    如果您需要进一步优化此方法，我建议：

    • 在常规循环中实现它，无需递归。因此，可以通过“切割”第一个元素来避免所有操作。
    • Dictionary<string,Node>存储字典（ ）而不是子节点列表。这将使按名称查找节点变得更加容易。请注意，这将丢失节点的顺序。如果节点按顺序排列很重要，那么您可以同时维护列表和字典。

    结果会是这样的：

    for(var name : path) 
{
    node.Children.TryGetValue(name, out var childNode);
    if(childNode==null) 
    { 
         childNode = new Node(name);
         node.Children[name] = childNode;
    }
    node = childNode;
}
    • 2

相关问题