Поиск в бинарном дереве через рекурсию - C#
Формулировка задачи:
Здравствуйте!
Подскажите пожалуйста... Мне нужно организовать поиск в бинарном дереве через рекурсию. Добавление то работает(вроде бы) нормально, а вот поиск почему то зацикливается...
В общем-логика примерно следующая:
Если текущий элемент не равен Null, тогда мы сравниваем его Value(значение) с тем, что мы ищем через CompareTo(в бинарном дереве требуется хранить классы, реализующие интерфейс IComparable). Если результат равен 0(т.е. обе записи одинаковые по сравниваемым критериям)-то мы вернём ветвь с этим элементов. В противном же случае-мы вызываем этот же метод из других ветвей в зависимости от результата CompareTo.
Вот весь код программы:
Ошибка происходит конкретно в этом методе:
Листинг программы
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace ConsoleApplication2
- {
- class Program
- {
- class Tree<TYPE> where TYPE : IComparable
- {
- private TYPE Value;
- private Tree<TYPE> Up;
- private Tree<TYPE> Left;
- private Tree<TYPE> Right;
- public TYPE GetValue
- {
- get
- {
- return this.Value;
- }
- }
- public void Insert(TYPE Value)
- {
- if (this.Value == null) this.Value = Value;
- else
- {
- if (this.Value.CompareTo(Value) < 0)
- {
- if (this.Right == null) this.Right = new Tree<TYPE>(Value);
- else this.Right.Insert(Value);
- }
- else if (this.Value.CompareTo(Value) > 0)
- {
- if (this.Left == null) this.Left = new Tree<TYPE>(Value);
- else this.Left.Insert(Value);
- }
- else if (this.Value.CompareTo(Value) == 0) Console.WriteLine("Невозможно добавить одинаковый элемент");
- }
- }
- public Tree<TYPE> Search(TYPE Value)
- {
- if (this != null)
- {
- if (this.Value.CompareTo(Value) == 0) return this;
- else if (this.Value.CompareTo(Value) > 0) this.Left.Search(Value);
- else if (this.Value.CompareTo(Value) < 0) this.Right.Search(Value);
- }
- return null;
- }
- public Tree()
- {
- this.Up = null;
- this.Left = null;
- this.Right = null;
- }
- public Tree(TYPE Value)
- {
- this.Up = null;
- this.Left = null;
- this.Right = null;
- this.Value = Value;
- }
- }
- class MyClass : IComparable
- {
- private Int32 Value = new Int32();
- public Int32 CompareTo(object Data)
- {
- if (this.Value == (Data as MyClass).Value) return 0;
- else if (this.Value > (Data as MyClass).Value) return 1;
- else return -1;
- }
- public MyClass()
- {
- this.Value = new Int32();
- }
- public MyClass(Int32 Value)
- {
- this.Value = Value;
- }
- }
- static void Main(string[] args)
- {
- Tree<MyClass> Data = new Tree<MyClass>(new MyClass(50));
- Data.Insert(new MyClass(45));
- Data.Insert(new MyClass(59));
- Data.Insert(new MyClass(15));
- Data.Insert(new MyClass(53));
- Data.Insert(new MyClass(83));
- Data.Insert(new MyClass(33));
- Data.Insert(new MyClass(22));
- Data.Insert(new MyClass(1));
- Console.WriteLine(Data.Search(new MyClass(53)).GetValue.ToString());//Вот здесь и происходит "зацикливание"...
- Console.ReadKey();
- }
- }
- }
Листинг программы
- public Tree<TYPE> Search(TYPE Value)
- {
- if (this != null)
- {
- if (this.Value.CompareTo(Value) == 0) return this;
- else if (this.Value.CompareTo(Value) > 0) this.Left.Search(Value);
- else if (this.Value.CompareTo(Value) < 0) this.Right.Search(Value);
- }
- return null;//Если this == null-тогда и вернётся null. Если элемент не был найден-то и вернём пустую ссылку.
- }
Решение задачи: «Поиск в бинарном дереве через рекурсию»
textual
Листинг программы
- public Tree<TYPE> Search(TYPE Value)
- {
- int res=this.Value.CompareTo(Value);
- if(res == 0) return this;
- if(res>0)
- (
- if(this.Left!=null)
- return this.Left.Search(Value);
- }
- else
- {
- if(this.Right!=null)
- return this.Right.Search(Value);
- }
- return null;
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д