How to implement a non-beneath tree

Question

I had a problem with implementing a non-binary tree, where the root node can have an arbitrary number of child nodes. Basically, I would like some ideas on how to go about this, as I have the code written, but I am stuck on this issue, 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; } } 

}

Answer 1

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

Since I assume this is homework, let me give you the direction you should go. The data structure you want:

 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; } } 

Now we will redraw the diagram - vertical lines - "first child", horizontal lines - "next brother"

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

Make sense?

Now, can you write the code that creates this tree using this data structure? Start with the rightmost leaves and pave the way to 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 ... 

Note that an arbitrary tree is just a 45 degree rotated binary tree, where the root never has a “right” child. Binary trees and arbitrary trees are one and the same ; you just assign different meanings to two children.

Answer 2

Since you cannot use the collection, why not 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 as follows:

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

Now you will have:

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

Then you will need to implement various functions (getters, removers, etc.). But this is your job.

Answer 3

If you cannot use any collections, keep the link in all the children of the parent. You can simulate your chart using the following data structure:

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

Now you can have as many children as possible for each node:

 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); 

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; } } 

Answer 5

You can imagine a multi-level tree using the node type, which has only the following pointer and a child pointer.

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

The node child pointer is used to indicate the first child of a node.

Here is a sample code that demonstrates how to do this. It does not contain error handling and is not intended to be a complete solution, but you must compile it and, if necessary, run it under the debugger to fully understand how it works.

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

Note that the node type is common in this example, and I use it only to store string data. You can simply replace T with the type you want if you don't need 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 read this answer before writing this, I probably wouldn't have bothered - but I already wrote this, and I didn't want to just throw it away.)

Answer 6

Some random ideas:

• A node will need some list of child nodes, consider using a concurrency-protected implementation, most likely IEnumerable<NodeType> will correspond to a vector
• You may or may not want a parent pointer - conisder for faster (read: not too lame) traversal
• I recommend that you create a NodeType<T> to make life easier when using the tree