c# - 检查树路径中节点的最佳算法？

Question

假设我有这棵树：

           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;

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

Answer 1

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

编辑：是这样的：

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

1. 确实，一定要为此使用递归。
2. 如果您使用递归方法，则可以设置一个（静态）成员变量，如结果并检查每次迭代是否已设置。如果设置，只需跳出方法（返回）以停止递归进一步运行。