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

Question

如何编写符合这些要求的代码？这是问题： 检查树 T 中是否存在键为 K 的节点，如果存在，return 对该节点的引用。如果树为空，则报告未找到该节点并停止。否则，比较K和根节点X的键值。

如果K=X，向该节点发出link并停止。
若K>X，递归查找T的右子树中的key K
如果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 可以 return 任何数字，而不仅仅是 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;
    }

另请参阅 how to transform a recursive method to an iterative one 以更通用的方式。请注意，该示例使用堆栈，在您的情况下不需要堆栈，因为您只处理树的一个分支。

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

binary search tree (BST) find method in C#

c#

data-structures

binary-tree

binary-search-tree