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;
}
}
}
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.
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.
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);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With