C#中的二进制搜索树(BST)查找方法

Question

如何编写具有这些要求的代码？这就是问题所在：检查树T中是否存在关键字为K的节点，如果存在，则返回对此节点的引用。如果树为空，则报告未找到节点并停止。否则，将K与根节点X的键值进行比较。

• 如果K=X，则发出到此节点的链接并停止
• 如果K>X、 递归地搜索T的右子树中的关键字K
• 如果K<X、 递归地搜索T的左子树中的关键字K

这就是我发现的：

public GenBT<T> Find(GenBT<T> k, T inf){ 
if (k == null) return null; 
else 
switch (inf.CompareTo(k.inf)){ 
case 1: return Find(k.RT, inf); 
case -1: return Find(k.LT, inf); 
case 0: return k; 
default: return null;} 
};

但我也发现，如果我想在BST中搜索或查找，我必须使用这样的代码：

struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");

while(current->data != data){

if(current != NULL) {
printf("%d ",current->data);

//go to left tree
if(current->data > data){
current = current->leftChild;
}  //else go to right tree
else {                
current = current->rightChild;
}

//not found
if(current == NULL){
return NULL;
}
}         
}

return current;
}

这两种看起来非常不同，我不知道哪种方法是正确的，一般来说，解决这个问题的正确方法是什么

Answer 1

要将递归解决方案转换为迭代解决方案，我们需要插入一个循环。在递归的情况下，我们为每次递归更改节点参数。在迭代的情况下，我们只需创建一个更新的变量，而不是递归。

更改了命名，使示例更加清晰和可编译。请注意，CompareTo可以返回任何数字，而不仅仅是0、1和-1。所以一个开关是不够的：

public class Node<T>
{
public Node<T> Left { get; }
public Node<T> Right { get; }
public T Value { get; }
public Node(Node<T> left, Node<T> right, T value)
=> (Left, Right, Value) = (left, right, value);
}
public static Node<T> Find<T>(Node<T> root, T target) where T : IComparable<T>
{
var current = root;
while (current != null)
{
var comparison = target.CompareTo(current.Value);
if (comparison > 0) 
current = current.Right;
else if (comparison < 0)
current = current.Left;
else
return current;
}
return null;
}

另请参阅如何以更通用的方式将递归方法转换为迭代方法。请注意，该示例使用堆栈，在您的情况下不需要堆栈，因为您只处理树的一个分支。