Поиск в бинарном дереве через рекурсию - 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; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д