почему у меня выходит Stackoverflow exception, при попытке применения метода RotateLeft() для экземпляра класса BinarySearchTree А? Проблема именно в этом методе, но я не понимаю, почему у меня постоянно выводит 30 (30, 30, 30, 30, 30 и т.д), если я поменял ссылки и у меня должно после 30 идти 54 и т.д ?
class Node<T>
{
internal T value;
public int Balance
{
get
{
if (Left == null && Right == null)
return 0;
else if (Left == null && Right != null)
return 0 - Right.Height;
else if (Left != null && Right == null)
return Left.Height;
return (Left.Height - Right.Height);
}
private set { }
}
public int Height
{
get
{
if (Left == null && Right != null)
return 1 + Right.Height;
else if (Left != null && Right == null)
return 1 + Left.Height;
else if (Left != null && Right != null)
{
if (Left.Height >= Right.Height)
return Left.Height + 1;
else
return Right.Height + 1;
}
else
return 0;
}
private set
{
}
}
public Node<T> Right;
public Node<T> Left;
public Node(T value)
{
this.value = value;
Right = null;
Left = null;
}
}
class BinarySearchTree<T> where T : IComparable
{
public Node<T> root;
public Node<T> Root { get { return root; } set { } }
public void Traverse()
{
TraversalRec(root);
}
public void RotateRight(ref Node<T> root)
{
// new root = root.Left
// new root's right = old root;
// new root right's left is its previous right;
// root's left is still the same;
Node<T> t = root;
t.Left = t.Left.Right;
root = root.Left;
root.Right = t;
}
public void RotateLeft(ref Node<T> root)
{
// new root = root.Right;
// new root's left = old root;
// new root's left's right is its previous left;
// root's right is still the same;
Node<T> t = root;
t.Right = root.Right.Left;
root = root.Right;
root.Left = t;
}
private void TraversalRec(Node<T> root) // not done yet
{
if (root.Left != null)
{
TraversalRec(root.Left);
}
Console.Write(root.value + ", ");
if (root.Right != null)
{
TraversalRec(root.Right);
}
}
public BinarySearchTree()
{
root = null;
}
public Node<T> Search(T value)
{
return SearchRec(value, root);
}
private Node<T> SearchRec(T value, Node<T> root)
{
if (root == null)
return null;
if (root.value.Equals(value))
return root;
else if (root.value.CompareTo(value) > 0)
return SearchRec(value, root.Left);
else
return SearchRec(value, root.Right);
}
public bool Add(T value)
{
return AddRec(value, ref root);
}
private bool AddRec(T value, ref Node<T> root)
{
if (root == null)
{
root = new Node<T>(value);
return true;
}
else if (value.CompareTo(root.value) > 0)
return AddRec(value, ref root.Right);
else if (value.CompareTo(root.value) <= 0)
return AddRec(value, ref root.Left);
return false;
}
private Node<T> ReplaceWithSmallest(ref Node<T> rootReplace, ref Node<T> rootSmallest) // rootReplace - what to replace, rootSmallest - its right child.
{
if (rootSmallest.Left != null)
{
return ReplaceWithSmallest(ref rootReplace, ref rootSmallest.Left);
}
else
{
rootSmallest.Left = rootReplace.Left;
rootSmallest.Right = rootReplace.Right;
rootReplace = rootSmallest;
rootSmallest = null;
return rootReplace;
}
}
public Node<T> Remove(T value)
{
return RemoveRec(ref root, ref root, value);
}
private Node<T> RemoveRec(ref Node<T> root, ref Node<T> ParentElem, T value)
{
if (root.value.CompareTo(value) == 0) // the element has been found
{
if (root.Left != null && root.Right != null)
return ReplaceWithSmallest(ref root, ref root.Right); // replace current root element with the element that this function is going to find (second parameter)
else if (root.Left != null && root.Right == null) // if there's 1 child there
{
if (ParentElem.Left.Equals(root)) // if our element is its parent's left son
ParentElem.Left = root.Left;
else
ParentElem.Right = root.Left;
}
else if (root.Left == null && root.Right != null)
{
if (ParentElem.Left.Equals(root))
ParentElem.Left = root.Right;
else
ParentElem.Right = root.Right;
}
else if (root.Left == null && root.Right == null)
root = null;
}
else if (value.CompareTo(root.value) > 0) // if the value we're looking for is bigger than current element
{
return RemoveRec(ref root.Right, ref root, value); // then go to its right child
}
else if (value.CompareTo(root.value) < 0)
{
return RemoveRec(ref root.Left, ref root, value); // otherwise go to its left child
}
return root;
}
}
class IntBinarySearchTree : BinarySearchTree<int>
{
}
class Program
{
static void Main(string[] args)
{
IntBinarySearchTree A = new IntBinarySearchTree();
A.Add(30);
A.Add(54);
A.Add(55);
A.Add(53);
A.Traverse();
A.RotateLeft(ref A.root);
A.Traverse();
//A.Remove(A.Root.value);
//Console.WriteLine(A.Root.value);
//Console.WriteLine(A.Root.Right.Right.Left);
Console.WriteLine("\r" + A.Root.Height);
Console.WriteLine(A.Search(30).Balance);
Console.WriteLine(A.Search(54).Balance);
Console.WriteLine(A.Search(20).Balance);
Console.ReadKey();
}
}
это потому, что в памяти хранится ссылка на объект, а не он сам, поэтому когда я менял другой объект, которому я присвоил "значение" (на самом деле ссылку) другого объекта, менялся один и тот же самый объект, второго просто не существовало, просто было две ссылки.
Правильное решение двух методов:
public void RotateRight()
{
// 1. new root = old root.Left
// 2. old root.Left = null; old root.Left = old root.Left.Right
// 3. new root.Right = old root;
Node<T> newRoot = new Node<T>(root.Left);
root.Left = root.Left.Right;
newRoot.Right = new Node<T>(root);
root = newRoot;
}
public void RotateLeft()
{
// 1. new root = old root.Right
// 2. old root.Right = null; old root.Right = old root.Right.Left
// 3. new root.Left = old root;
Node<T> newRoot = new Node<T>(root.Right);
root.Right = root.Right.Left;
newRoot.Left = new Node<T>(root);
root = newRoot;
}
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Перевод документов на английский язык: Важность и ключевые аспекты
Всем приветЕсть текст, как сделать так, чтобы он записался в List<List<string>>,где List<List<string>> - Предложение, а List<string> - Слова?
Подскажите, актуален ли сейчас WPF, как фреймворк для написания настольных приложений или есть что-то более стильное, модное и молодежное?
Имеется срочная необходимость разбить русский текст из файла на предложенияПростое деление (split) по
Необходимо выбрать из базы данных строку с именем admin и паролем 1234, в программировании не особо понимаю, рассчитываю на Вашу помощь, заранее...