2012-02-16 100 views
2

我可以有相同的类型如何执行递归搜索?

public class Task 
{ 
    public DateTime Start { get; set;} 
    public DateTime Finish { get; set;} 
    public List<Task> Tasks {get; set;} 
    public DateTime FindTaskStartDate(Task task) 
    {} 
} 

我应该如何执行递归搜索(LINQ也许)找到与最早开始日期的任务的子任务的任务类?

我最初的做法涉及太多的循环,它结束变得有点混乱,并迅速螺旋失控。这是我的第二次尝试:

public DateTime FindTaskStartDate(Task task) 
{ 
    DateTime startDate = task.Start; 

    if(task.HasSubTasks()) 
    { 
     foreach (var t in task.Tasks) 
     { 
      if (t.Start < startDate) 
      { 
       startDate = t.Start; 

       if (t.HasSubTasks()) 
       { 
        //What next? 
        //FindTaskStartDate(t); 
       } 
      } 
     } 
    } 

    return startDate; 
} 

任何更好的解决方案,那里解决这个问题?

感谢

+0

执行递归搜索的最佳方法是...使用递归搜索。 – 2012-02-16 02:44:50

回答

6

你说得对,递归这里是正确的做法。像这样的东西应该工作:

public DateTime FindTaskStartDate(Task task) 
{ 
    DateTime startDate = task.Start; 

    foreach (var t in task.Tasks) 
    { 
     var subTaskDate = FindTaskStartDate(t); 
     if (subTaskDate < startDate) 
      startDate = subTaskDate; 
    } 

    return startDate; 
} 

我删除了检查为task.HasSubTasks(),因为它只是使代码更复杂,没有任何额外的好处。

如果您发现自己经常编写需要遍历树中所有任务的代码,那么您可能希望使其更通用。例如,您可以有一个返回IEnumerable<Task>的方法,该方法返回树中的所有任务。然后找到最小的开始日期将是一样容易:

IterateSubTasks(task).Min(t => t.Start) 
+0

准确地说我是怎么写的,尽管subTaskDate可能应该是DateTime类型:) – 2012-02-16 02:17:59

+1

@Ryan Gibbons:你可以使用[var](http:// msdn。microsoft.com/en-us/library/bb383973.aspx)而没有指定实际的类型,它会工作得很好。它的类型是隐式确定的。 – Bernard 2012-02-16 02:21:03

+0

+1。为您提供Fixer对当前问题的所有需求。 – 2012-02-16 02:23:03

0

分离遍历所有树的搜索,如果有你想上的所有项目执行其他任务,可能是有益的。即如果您通过树项目实现IEnumerable,则可以使用LINQ查询来搜索任何您想要的内容或对您树中的所有任务执行其他操作。 检查出Implementing IEnumerable on a tree structure的方式来做到这一点。

14

Svick的解决方案很好,但我想我会添加一些更一般的建议。看起来你是写新递归方法的新手,并且在那里挣扎了一下。写一个递归方法最简单的办法就是严格遵循一个模式:

Result M(Problem prob) 
{ 
    if (<problem can be solved easily>) 
     return <easy solution>; 
    // The problem cannot be solved easily. 
    Problem smaller1 = <reduce problem to smaller problem> 
    Result result1 = M(smaller1); 
    Problem smaller2 = <reduce problem to smaller problem> 
    Result result2 = M(smaller2); 
    ... 
    Result finalResult = <combine all results of smaller problem to solve large problem> 
    return finalResult; 
} 

因此,假设你要解决的问题“什么是我的二叉树的最大深度是多少?”

int Depth(Tree tree) 
{ 
    // Start with the trivial case. Is the tree empty? 
    if (tree.IsEmpty) return 0; 
    // The tree is not empty. 
    // Reduce the problem to two smaller problems and solve them: 
    int depthLeft = Depth(tree.Left); 
    int depthRight = Depth(tree.Right); 
    // Now combine the two solutions to solve the larger problem. 
    return Math.Max(depthLeft, depthRight) + 1; 
} 

您需要三样东西,使递归工作:

  • 这个问题有你递归每一次得到的。
  • 问题必须最终变得很小以至于无需递归即可解决
  • 该问题必须通过将问题分解为一系列较小的问题,解决每个问题并合并结果来解决。

如果不能保证这三样东西,然后不使用递归解决方案

+0

当然,对于第三个先决条件,对于某些问题,该系列可能永远不会有多个元素。一个例子是不变列表的长度:'int Length {get {return this.IsEmpty? 0:this.Tail.Length + 1; }} – phoog 2012-02-16 18:30:37