почему у меня выходит stackoverflow exception

195
28 мая 2018, 09:00

почему у меня выходит 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();
    }
}
Answer 1

это потому, что в памяти хранится ссылка на объект, а не он сам, поэтому когда я менял другой объект, которому я присвоил "значение" (на самом деле ссылку) другого объекта, менялся один и тот же самый объект, второго просто не существовало, просто было две ссылки.

Правильное решение двух методов:

   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;
    }
READ ALSO
Запись List&lt;string&gt; в List&lt;List&lt;string&gt;&gt;

Запись List<string> в List<List<string>>

Всем приветЕсть текст, как сделать так, чтобы он записался в List<List<string>>,где List<List<string>> - Предложение, а List<string> - Слова?

164
Актуальность WPF

Актуальность WPF

Подскажите, актуален ли сейчас WPF, как фреймворк для написания настольных приложений или есть что-то более стильное, модное и молодежное?

260
Разбить текст на предложения C#

Разбить текст на предложения C#

Имеется срочная необходимость разбить русский текст из файла на предложенияПростое деление (split) по

244
Нужно отобразить кнопки найдя строку &ldquo;admin&rdquo; и пароль &ldquo;1234&rdquo; в БД

Нужно отобразить кнопки найдя строку “admin” и пароль “1234” в БД

Необходимо выбрать из базы данных строку с именем admin и паролем 1234, в программировании не особо понимаю, рассчитываю на Вашу помощь, заранее...

180