An addition to a binary tree is wrong.



  • Trying to get a red black tree on C#. I'm trying to create a typical binary tree. Problem with the wrong addition of the element in the tree. The good record shows that the right-holder is being added at all times. Here's the tree class:

    class MyTree
    {
        public int number;       
        public MyTree left;
        public MyTree right;
    }
    

    This is the class in which the addition is implemented:

        class TreeDictionary
    {
        public void Insert(int key, MyTree tree)
        {          
            if (tree == null)
            {
                tree = new MyTree();
                tree.number = key;
                tree.left = null;
                tree.right = null;
            }
            else
            {
                Console.WriteLine("{0} {1}", key, tree.number);
                if (key <= tree.number)
                {
                    Console.WriteLine("Left");
                    Insert(key, tree.left);
                }
                else
                {
                    Console.WriteLine("Right");
                    Insert(key, tree.right);
                }
            }
        }
    


  • if (tree == null)
    {
        tree.number = key;
        ...
    

    Just saying out loud, what you're trying to do:

    If referred to the facility MyTree In fact, it does not refer to any object, try to cross this zero reference. (and change anything in this very object, in your case the field number)

    How to fix this in the context of the task, I think you will.


    Update on comments


    The simplest and most convenient way to write a code of this type - To agree (i.e. organise some Code Contractthat reference to the object MyTreetransmitted method Insert - Never. null

    Subject to this contract, the code becomes quite simple:

    public static void Insert(int key, MyTree node)
    

    {
    if (key <= node.key)
    {
    if (node.left == null)
    {
    // Можно оформить как конструктор 'MyTree(int key)'.
    node.left = new MyTree();
    node.left.key = key;
    // Ссылки left, right автоматически проинициализированы как null.

            return;
            // Рекурсия автоматически закончится после 'return'.
        }
    
        Insert(key, node.left);
    }
    else
    {
        // Абсолютно аналогично.
    }    
    

    }

    To comply with this contract in the context of the task (not transmitted by method null) The root of the tree must be constructed on its own.

    It is clear that the contract may be eliminated, but in that case, The design of the class needs to be somewhat different.




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2