binary tree in C#

Question

How would you do a binary tree in C# that is simple, straight forward, and does not use any predefined classes? I am talking about something simple like you would do in C++

Nothing like NGenerics Objects that represent trees

I mean something that starts with something simple, like this:

struct
{
  Node * left
  Node * right
  int value;
}

Follow up question:

OK, so if I have this:

public class binarytreeNode
{
    public binarytreeNode Left;
    public binarytreeNode Right;
    public int data;

}

Would I have to put the methods that act upon the node, inside this class? Doesn't this make this no longer a Node?

If I create a method for adding a node inside the Program class:

class Program
{       
     public binarytreeNode AddNode(int value)
    {
        binarytreeNode newnode = new binarytreeNode();
        newnode.Left = null;
        newnode.Right = null;
        newnode.data = value;
        return newnode;
    }
     static void Main(string[] args)
    {
        binarytreeNode head = AddNode(4);

    }
}

The compiler says that an object reference is required for my call to AddNode. Why?

Couldn't you just make a class like that, add methods as necessary, and write your tree? — Nik, Jun 01 '11 at 04:09
no it is not a homework assignment. I have done this in C++ but not in C# and I am trynig to learn on my own. — xarzu, Jun 01 '11 at 04:37

user541686 · Answer 1 · 2011-06-01T04:44:23.820

9

class Node<T>
{
    public Node<T> Left, Right;
    public T Value;
}

edited Jun 01 '11 at 04:44

answered Jun 01 '11 at 04:09

user541686

205,094
128
528
886

1

Although I find it sort of offensive to 'stack' declarations, also `Left`, `Right` should be of type `Node` (or it won't even compile) and there may be a point for restricting `T` to something that is `IComparable` for ordering. – Jun 01 '11 at 04:13
1

I like the generic, great suggestion. – Nik Jun 01 '11 at 04:14
why use the generic for the node and also for the value? – xarzu Jun 01 '11 at 04:29
1

@pst: Whoops, fixed that generic issue, thanks for pointing it out. As for making `T` be `IComparable`: That's not always a good idea, since the external code should be able to provide its own `IComparer` otherwise. And lol, why do you find that offensive? xD @xarzu: Not sure what you mean, sorry... would you mind clarifying? – user541686 Jun 01 '11 at 04:45
@Mehdrad It's just against my *personal* coding style ;-) Nothing wrong with it otherwise. – Jun 01 '11 at 04:52
@Mehrdad, why public T Value and not public int Value? – xarzu Jun 01 '11 at 05:03
@pst: Haha okay. I guess I should've also made them properties but w/e. :) @xarzu: Oooh -- because what if you wanted to store a different type? You shouldn't rewrite an entire container just because you decide to store more than one kind of data in it; that's the problem that generics solve. – user541686 Jun 01 '11 at 05:23

score 5 · Answer 2 · answered Jun 01 '11 at 04:10

5

class Node
{
  public Node left, right;
  public int value;
}

answered Jun 01 '11 at 04:10

Blindy

65,249
10
91
131

so C# would not make use of pointers here? Why? – xarzu Jun 01 '11 at 04:29
@xarzu: `class`es are implicitly pointers (more properly called "reference types") in C#. `struct`s are "value types", like in C. – user541686 Jun 01 '11 at 04:46
@xarzu, If you're familiar with pointers, then it's easy to understand references. `Node` in C# is equivalent to `Node **` in C/C++. The first level of indirection moves around as the .NET garbage collector rearranges memory and the 2nd level of indirection stays still while pointing at the moving pointer so you can always find your object. – Blindy Jun 01 '11 at 15:35

score 2 · Answer 3 · answered Jun 01 '11 at 05:07

namespace ConsoleApplication1
{
    public class binarytreeNode
    {
        public binarytreeNode Left;
        public binarytreeNode Right;
        public int data;

    }
    public class binarytree
    {
        public binarytreeNode AddNode(int value)
            {
                binarytreeNode newnode = new binarytreeNode();
                newnode.Left = null;
                newnode.Right = null;
                newnode.data = value;
                return newnode;
            }
    }
    class Program
    {       

         static void Main(string[] args)
        {
            binarytree mybtree = new binarytree();

            binarytreeNode head = mybtree.AddNode(4);

        }
    }
}

binary tree in C#

3 Answers3