检查树路径中节点的最佳算法

本文关键字：最佳 算法 节点 路径 检查 | 更新日期: 2023-09-27 18:31:03

假设我有这棵树：

           O-ROOT
         /        '
    O-A            O-B
     /          /       '
O-A1        O-B1        O-B2

我想在 C# 中执行此操作： 

1. Check every node starting from root (I think the best way is trought recursion?);
2. If I found a node with value = "Hello", return true and STOP the searching function;

你能帮我制定最好的算法吗？

检查树路径中节点的最佳算法

bool FindHello(Node node)
{
    if (node.Content == "Hello")
        return true;
    foreach (Node c in node.Children)
        if (FindHello(c))
            return true;
    return false;
}

我认为解决您的问题的最佳方法是使用广度优先搜索。它编写简单，并且尽可能有效。

编辑：像这样：

public bool Search(TreeNode node, string searchString)
{
   Queue<Control> q = new Queue<Node>();
   q.Enqueue(node);
   while(!q.empty()) {
     Node current = q.Dequeue();
     foreach(var childNode in node.Children)
       if(childNode.Content.CompareTo(searchString) == 0) {
         return true;
       }
       q.Enqueue(childNode);
     }
   }
   return false;
}

你对递归是正确的，请参阅深度优先或广度优先搜索算法。对于树来说，这要容易得多，因为您没有保留已访问过的节点的列表。

public bool Search(TreeNode node, string searchString)
{
   if(node.Value == searchString) return true;
   foreach(var childNode in node.Children)
     if(Search(childNode, searchString)) return true;
   return false;
}

广度优先搜索和深度优先搜索是最流行的（以及其他）树搜索技术之一，因此您可以从那里开始。此外，如果树中的每个节点最多有 2 个节点，并且它们以某种方式排序，则可以使用二叉搜索树技术。

  1. 事实上，一定要为此使用递归。
  2. 如果您使用的是递归方法，则可以设置一个（静态）成员变量，例如 result，并检查每次迭代是否设置。如果设置，只需跳出方法（返回）即可停止递归进一步运行。
相关文章：