How to implement a Non-Binary tree

Question

I am having trouble implementing a non-binary tree, where the root node can have an arbitrary amount of child nodes. Basically, I would like some ideas on how where to go with this, since I do have some code written, yet I'm stuck at this point on what to do next. BTW I cannot use any of the Collections classes at all. I can only use System.

using System;

namespace alternate_solution
{
 //            [root]
 //        /  /      \    \
 //    text  text  text  text

class Node//not of type TreeNode (since Node is different from TreeNode)
{
    public string data;
    public Node child;

    public Node(string data)
    {
        this.data = data;
        this.child = null;
    }

}

}

Napiform

Its supposed to be practice to prepare for a another project. Can I use a linked list of nodes? – Napiform

Sure you can use your own home-grown link list for nodes. – Preposterous

The I can only useSystem constraint needs an explanation. Also, what operations are needed? Insert, Remove at arbitrary positions? – Haaf

Remove is not needed, the only thing it should be able to do is to Insert at arbitrary positions. – Napiform

Sounds like you might be looking for a B+ Tree... – Lardaceous

Hint: A binary tree has two references to other tree nodes called Left and Right. An arbitrary tree has two references to other tree nodes called FirstChild and NextSibling. Aribitrary trees are binary trees; you just assign different meanings to the nodes. – Toaster

@EricLippert ' An arbitrary tree has two references to other tree nodes called FirstChild and NextSibling '. Out of my ignorance, what if you have more than two children? – Congruency

@RamiShareef: Then the first child has a sibling, and that sibling has a sibling, and so on, until you have a sufficient number of children. Consider reading my answer. – Toaster

Answer 1

So far Jerska's solution is the best but it is needlessly complicated.

Since I assume this is a homework exercise let me give you the direction you should head in. The data structure you want is:

class TreeNode
{
  public string Data { get; private set; }
  public TreeNode FirstChild { get; private set; }
  public TreeNode NextSibling { get; private set; }
  public TreeNode (string data, TreeNode firstChild, TreeNode nextSibling)
  {
    this.Data = data;
    this.FirstChild = firstChild;
    this.NextSibling = nextSibling;
  }
}

Let's now redraw your diagram -- vertical lines are "first child", horizontal lines are "next sibling"

Root
 |
 p1 ----- p2 ----- p4 ----- p6  
 |        |         |       |
 c1       p3       c4       p7
          |                 |
          c2 - c3           c5

Make sense?

Now, can you write code that produces this tree using this data structure? Start from the rightmost leaves and work your way towards the root:

TreeNode c5 = new TreeNode("c5", null, null);
TreeNode p7 = new TreeNode("p7", c5, null);
TreeNode p6 = new TreeNode("p6", p6, null);
... you do the rest ...

Notice that an arbitrary tree is just a binary tree "rotated 45 degrees", where the root never has a "right" child. Binary trees and arbitrary trees are the same thing; you just assign different meanings to the two children.

Toaster

It looks like I will consider this approach. Since there seems to be countless ways to represent an arbitrary tree, I believe that a more straightforward look at it makes sense. Thanks for the help! Just one question, to write out all the nodes in the tree, should I add all the Nodes in a linked list or is it not necessary? – Napiform

@KarimOumghar: That's unnecessary; you can easily write a recursive traversal of this tree, the same way you can write a recursive traversal of a binary tree. – Toaster

I've been looking for a similar solution, and this is really neat, I'll definitely use it. I have one concern though: in your implementation, you add nodes from the bottom-up, and I don't think your method allows adding a new node, because the TreeNodes have a private set, so you can't modify an existing node from outside of the class to accommodate a new child or sibling. How would you suggest adding a new node using this implementation? – Botchy

@leoking you can make the tree mutable or you can rewrite the spine to produce a new tree on insert. That works better with a normal binary tree than with one of these arbitrary trees, but it is pretty straightforward. – Toaster

By making the tree mutable, would that just mean changing the access for the fields? Also, what do you mean by the spine in this context? – Botchy

@leoking a comment is not a good place for a tutorial on immutable data structures. Try reading the immutable tag on my msdn blog and see if that helps. – Toaster

@EricLippert: "Binary trees and arbitrary trees are the same thing". However, if I want to go from Root to P6 I have to traverse P1, P2 and P4, while in the original graph it was a direct reference. It seems to me that the performances of these two trees are different. – Shorthanded

@LucaCremonesi: I just saw your comment now, four years later. Sure. Now suppose you have a reference to an arbitrary node in an n-ary tree and the question is "what is your sibling to the right?" That's a direct reference in my scheme, and an expensive tree searching problem in a tree where every node has an array of children if you don't know ahead of time the parent node and index. Different data structures have different performance characteristics for different operations; there is no one choice that is "the best" for all possibilities. – Toaster

@EricLippert: thank you for your reply, I am always interested in your comments and thoughts. However, not considering the performance, your binary tree has different relationships and hierarchy than the original arbitrary tree. Now P2, P4, P6 are all children (or grand-children) of P1, that is the relational semantic is different. [continue] – Shorthanded

@EricLippert: Questions about parent-child relationship now have different answers than in the previous arbitrary tree. The model you are using to represent these relationships is different and not equivalent to the original one. Nor you can recreate the original model from the new one. – Shorthanded

@LucaCremonesi: I think you have misunderstood the data structure here. Think about it this way: every node has a linked list of its children. The "downward" reference refers to the oldest child. The "rightward" reference is the next-oldest sibling; it's the link in the linked list. We could similarly implement "every node has a List<Node> of children", or "every node has a Node[] of children"; my example just chooses linked list to illustrate that n-ary tree and binary tree are just two different semantics on the same data structure. – Toaster

@LucaCremonesi: In my example, P2, P4 and P6 are all children of P1. P2 is the oldest child, P4 is the middle child, and P6 is their youngest sibling. – Toaster

Answer 2

Since you can't use a collection, why don't you create your own list ?

class Child {
    Node node;
    Child next = null;

    public Child (Node node) {
        this.node = node;
    }

    public void addChild (Node node) {
        if (this.next == null)
            this.next = new Child (node);
        else
            this.next.addChild (node);
    }
}

class Node {
   public string data;
   public Child children = null;

   public Node (string data) {
       this.data = data;
   }

   public void addChild (Node node) {
       if (this.children == null)
           this.children = new Child (node);
       else
           this.children.addChild (node);
   }
}

And use it like this :

Node root = new Node ("Hey");
root.addChild (new Node ("you"));
root.addChild (new Node ("me"));

You'll now have :

          Node ("Hey")
        /             \
   Node ("you")     Node ("me")

Then you will need to implement different functions (getters, removers, etc.). But that's your job.

Baxie

Answer 3

If you can't use any Collections, store link in all child elements to parent. You can model your graph by using next data structure:

class Node
{
    public string Data { get; set; }
    public Node Parent { get; set; }

    public Node(string data, Node parent)
    {
        Data = data;
        Parent = parent;
    }
}

You can now have as many childs for each node, as you like:

var root = new Node("root", null);

var parent = new Node("parent", root);
var anotherParent = new Node("yetAnotherParent", root);

var child = new Node("Child", parent);
var anotherchild = new Node("anotherchild", parent);

Narbada

But then how can you make a Depth First Search ? – Baxie

@Baxie do you need it? Is that an explicit requirement? Why haven't you mentioned Breadth-First search? – Narbada

I'm not the author of the post, I was wondering if that would be possible. And however, I actually have the same wonder with a Breadth-First Search. – Baxie

@Baxie You simply can't. You still have to store links to all child elements and handling this kind of tree is very cubersome. But still, I find requirement "and hey, I can't use any of that collection stuff" very unreasonable. – Narbada

Answer 4

class Node
{
    public string data;
    public Node parent;
    public IEnumerable<Node> children;

    public Node(string data, Node parent, IEnumerable<Node> children)
    {
        this.data = data;
        this.parent = parent;
        this.children = children;
    }

}

Dextrogyrate

Answer 5

You can represent a multiway tree using a node type that has just a next pointer and a child pointer.

The node's next pointer is used to point to the next sibling child, implemented as a simple linked list.

The node's child pointer is used to point to the first child of the node.

Here's some sample code which demonstrates how to put this together. It does not contain any error handling and it isn't intended to be a complete solution, but you should be able to compile it and - if necessary - run it under the debugger to fully understand how it works.

I also added an example enumerable to show how you could iterate over the tree nodes. You will probably want to play around with this to produce results in different orders. IF using an enumerable is too complex for what you need, you will need to write your own simple recusive method to visit all the nodes.

Note that the node type is generic in this example, and I'm only using it to hold string data. You could just substitute T with the type you want if you don't want a generic type.

using System;
using System.Collections;
using System.Collections.Generic;

namespace Demo
{
    sealed class Node<T>
    {
        public T Data;  // Payload.

        public Node<T> Next;  // This will point to the next sibling node (if any), forming a linked-list.
        public Node<T> Child; // This will point to the first child node (if any).
    }

    sealed class Tree<T>: IEnumerable<T>
    {
        public Node<T> Root;

        public Node<T> AddChild(Node<T> parent, T data)
        {
            parent.Child = new Node<T>
            {
                Data = data,
                Next = parent.Child // Prepare to place the new node at the head of the linked-list of children.
            };

            return parent.Child;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return enumerate(Root).GetEnumerator();
        }

        private IEnumerable<T> enumerate(Node<T> root)
        {
            for (var node = root; node != null; node = node.Next)
            {
                yield return node.Data;

                foreach (var data in enumerate(node.Child))
                    yield return data;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    class Program
    {
        void run()
        {
            var tree = new Tree<string>();

            tree.Root = new Node<string>{Data = "Root"};

            var l1n3 = tree.AddChild(tree.Root, "L1 N3");
            var l1n2 = tree.AddChild(tree.Root, "L1 N2");
            var l1n1 = tree.AddChild(tree.Root, "L1 N1");

            tree.AddChild(l1n1, "L2 N1 C3");
            tree.AddChild(l1n1, "L2 N1 C2");
            var l2n1 = tree.AddChild(l1n1, "L2 N1 C1");

            tree.AddChild(l1n2, "L2 N2 C3");
            tree.AddChild(l1n2, "L2 N2 C2");
            tree.AddChild(l1n2, "L2 N2 C1");

            tree.AddChild(l1n3, "L2 N3 C3");
            tree.AddChild(l1n3, "L2 N3 C2");
            tree.AddChild(l1n3, "L2 N3 C1");

            tree.AddChild(l2n1, "L3 N1 C3");
            tree.AddChild(l2n1, "L3 N1 C2");
            tree.AddChild(l2n1, "L3 N1 C1");

            tree.Print();
        }

        static void Main()
        {
            new Program().run();
        }
    }

    static class DemoUtil
    {
        public static void Print(this object self)
        {
            Console.WriteLine(self);
        }

        public static void Print(this string self)
        {
            Console.WriteLine(self);
        }

        public static void Print<T>(this IEnumerable<T> self)
        {
            foreach (var item in self)
                Console.WriteLine(item);
        }
    }
}

(I know this is similar to Eric's answer above, and if I'd read that answer before writing this one I probably wouldn't have bothered - but I'd already written this and I didn't want to just throw it away.)

Spur

Answer 6

Some random ideas:

• A node will need some sort of list of the child nodes, consider using a concurrency-proof implementation, most likely IEnumerable<NodeType> will fit the bill
• You might or might not want a backpointer to the parent - conisder one for speedy (read: not too lame) traversal
• I recommend you create a NodeType<T> to make life easier when consuming the tree

Cohin