按名称递归搜索二叉搜索树 [英] Recursively search binary search tree by name

问题描述

我有一个二叉搜索树，存储国家财务状况的详细信息，



i已经添加了所有国家现在我只想要通过countryname搜索它们



i在我的BST类中有一个find方法应该这样做但是它不起作用，当我调用它时它会打印任何东西;

  public   object  find（ string  country）
 {
  return  find（country，root ）; 
} 
 
 
 私人 对象 find（< span class =code-keyword> string  item，Node< T> tree）
 {
  int  compare; 
  while （tree！=  null ）
 {
  string  [] outcome = tree.Data.ToString（）。Split（' ）; 
比较=结果[ 0 ]。CompareTo（item）; 
  if （compare ==  0 ）
 {
  return  tree.Data; 
 
 
} 
 其他 如果（比较< span class =code-keyword>>   0 ）
 {
 tree = tree.Left; 
} 
 其他  if （比较<   0 ）
 {
 tree = tree.Right; 
} 
} 
 
 返回  null ; 

在我的表格课程中我也有这个代码

  public   object  findcountryInformation（ string  countryName）
 
 
 {
  object  result = myTree.find（countryName）; 
 
 返回结果; 
} 
 
 
 私有  void  button1_Click（< span class =code-keyword> object  sender，EventArgs e）
 {
 
 
  string  text = listBox1.GetItemText（listBox1.SelectedItem）; 
 
 
 
  object  result = findcountryInformation（text）; 
 
 
 
 Console.WriteLine（result）; 
 
}} 

预期输出应该是从列表框中选择的国家/地区的详细信息

  class  BSTree< T> ：BinTree< T> 其中 T：IComparable 
 {
  public  BSTree（）
 { 
 root =  null ; 
} 
 
  public   void  InsertItem（T item）
 {
 insertItem（item， ref  root）; 
} 
 
  private   void  insertItem（T item， ref 节点< T>树）
 {
  if （tree ==  null ）
 tree =  new 节点< T>（item）; 
 
  else   if （item.CompareTo（tree.Data）<   0 ）
 insertItem（item， ref  tree.Left）; 
 
  else   if （item.CompareTo（tree.Data）>   0 ）
 insertItem（item， ref  tree.Right）; 
 
} 
 
  private   int  max（< span class =code-keyword> int  x， int  y）
 {
  if （y >  x）
  return  y; 
 
  return  x; 
} 
 
  public   int 高度（）
 {
  return  height（root）; 
} 
 
  private   int  height（节点< T>树） ）
  //  返回树的最高级别 
 {
  if （tree ==  null ）
 返回  0 ; 
 返回  1  + max（height（tree.Left），height（tree.Right） ）; 
} 
 
  public   Boolean 包含（T item）
 {
节点< T> node = root; 
  return 包含（root，item）; 
} 
 
  private   Boolean 包含（Node< T>节点，T项）
 {
  if （node ==  null ）
 返回  false ; 
 
  //   if（node.Data == item） 
  if （item.CompareTo（node.Data）<   0 ）
  return 包含（node.Left，item）; 
  if （item.CompareTo（node.Data）>   0 ）
  return 包含（node.Right，item）; 
  return   true ; 
} 

节点类



<前lang = C＃> class 节点< T> 其中 T：IComparable

{

private T数据;
public 节点< T>左右;


public 节点（T项）
{
data = item;
剩余= null ;
Right = null ;
}
public T数据
{
set {data = value ; }
获取 {返回数据; }
}


}
}

我尝试了什么：



我已经尝试了一切我能想到的包括调试但我没有太多洞察力

解决方案

引用：

我已经尝试了所有我能想到的内容，包括调试，但我没有深入了解

至少，使用调试器，你应该能够看到 find 是否返回了什么，如果失败了，你会看到原因。
在没有数据的情况下说出其他内容很复杂。

首先，在这种情况下，您应该更喜欢非递归解决方案。树可以有任何深度，因此，从理论上讲，您可以面对堆栈溢出（甚至实际上，对于大数据集）。此外，递归可能会影响您的性能。迭代地对树进行完美搜索。



递归应该在更合适的情况下使用。比如，你有一些类的元数据（元类）。继承深度永远不会太高，因此您可以轻松地向任何方向走向层次结构。递归是好的还有很多其他情况。



现在，关于递归。看起来你不知道那是什么。否则你至少会尝试一下。请参阅：

递归 - 维基百科，免费的百科全书 [ ^ ]，

递归（计算机科学） - 维基百科，免费的百科全书 [ ^ ]。



目前还不是很清楚吗？如果没有，我不想给你整个解决方案。你真的需要自己做所有的基本工作，否则你什么都学不到。因此，您只需要一个提示：在执行代码的代码期间，您必须在其他地方调用 find - 节点。此外，您最终需要中断递归而不允许无限递归。请参阅：损坏的递归 [ ^ ]。 :-)



顺便问一下，你上面提到了我的说法吗？并不是说这个笑话真的很有趣，但在某种程度上，这是真的。另一件事很有趣：不仅是帖子谈论无限（或不是）递归，而且推测的本质是递归推理，也是无限。 :-)

-SA

i have a binary search tree that stores details of countries financial situation,

i have added all the countries now i just want to search them by countryname

i have a find method in my BST class that is supposed to do that but it doesnt work, it doesent print anything when i call it;

public object find(string country)
   {
       return find(country, root);
   }


   private object find(string item, Node<T> tree)
   {
       int compare;
       while (tree != null)
       {
           string[] outcome = tree.Data.ToString().Split(',');
           compare = outcome[0].CompareTo(item);
           if (compare == 0)
           {
               return tree.Data;


           }
           else if (compare > 0)
           {
               tree = tree.Left;
           }
           else if (compare < 0)
           {
               tree = tree.Right;
           }
       }

       return null;

in my form class i also have this code

public object findcountryInformation(string countryName)


    {
        object result = myTree.find(countryName);

        return result;
    }


    private void button1_Click(object sender, EventArgs e)
    {


        string text = listBox1.GetItemText(listBox1.SelectedItem);



        object result = findcountryInformation(text);



        Console.WriteLine(result);

}}

expected output should be details of the countries selected from the listbox

class BSTree<T> : BinTree<T> where T : IComparable
   {
       public BSTree()
       {
           root = null;
       }

       public void InsertItem(T item)
       {
           insertItem(item, ref root);
       }

       private void insertItem(T item, ref Node<T> tree)
       {
           if (tree == null)
               tree = new Node<T>(item);

           else if (item.CompareTo(tree.Data) < 0)
               insertItem(item, ref tree.Left);

           else if (item.CompareTo(tree.Data) > 0)
               insertItem(item, ref tree.Right);

       }

       private int max(int x, int y)
       {
           if (y > x)
               return y;

           return x;
       }

       public int Height()
       {
           return height(root);
       }

       private int height(Node<T> tree)
       //Return the max level of the tree
       {
           if (tree == null)
               return 0;
           return 1 + max(height(tree.Left), height(tree.Right));
       }

       public Boolean Contains(T item)
       {
           Node<T> node = root;
           return contains(root, item);
       }

       private Boolean contains(Node<T> node, T item)
       {
           if (node == null)
               return false;

           //if (node.Data == item)
           if (item.CompareTo(node.Data) < 0)
               return contains(node.Left, item);
           if (item.CompareTo(node.Data) > 0)
               return contains(node.Right, item);
           return true;
       }

node class

    class Node<T> where T : IComparable
        
    {
        
        private T data;
        public Node<T> Left, Right;


        public Node(T item)
        {
            data = item;
            Left = null;
            Right = null;
        }
        public T Data
        {
            set { data = value; }
            get { return data; }
        }


    }
}

What I have tried:

i've tried everything that i could think of including debugging but i didnt get much insight

解决方案

Quote:

i've tried everything that i could think of including debugging but i didnt get much insight

At least, using the debugger, you should be able to see if find returns something and what, if it fails, you will see why too.
It is complicated to say something else without the data.

First of all, you should prefer non-recursive solutions in such cases. A tree can have any depth, so, theoretically speaking, you can face stack overflow (and even practically, for big data sets). Also, recursion may compromise your performance. Trees are perfectly searched iteratively.

Recursion should be used in more appropriate situations. Say, you have some metadata with classes (meta-classes). The inheritance depth is never too high, so you can easily walk up the hierarchy in any direction. There are many other cases when recursion is good.

Now, about recursion. It looks like you don't know what is that. Otherwise you would at least try it. Please see:
Recursion — Wikipedia, the free encyclopedia[^],
Recursion (computer science) — Wikipedia, the free encyclopedia[^].

Isn't that clear already? If not, I don't want to give you the whole solution. You really need to do all the basic work all by yourself, otherwise you could not learn anything. So, you need only one hint: during execution of the code of find, you have to call find — on other node. Also, you need to break out of recursion eventually and not allow "infinite" recursion. Please see: Broken Recursion[^]. :-)

By the way, did you get my saying referenced above? Not that this joke is really funny, but, in a way, it's true. Another thing is funny: not only the post talks about "infinite" (or not) recursion, but the nature of the speculations is recursive reasoning, also "infinite". :-)

—SA

这篇关于按名称递归搜索二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！