Part 1 – Design and implement a binary tree using generics Design and implement
ID: 3761064 • Letter: P
Question
Part 1 – Design and implement a binary tree using generics
Design and implement a generic binary tree consisting of classes BT<T> and BTnode<T> and the interface BTinterface<T>.
The class BT<T> defines the instance variable root of type Node<T>, a default constructor which builds an empty tree and implements the methods specified by the interface BTinterface<T>.
The class Node<T> defines the instance variable value of type T, the instance variables left and right of type Node<T> representing references to the left and right child nodes, a constructor with parameter representing the value of the new node and a method getValue returning the node value.
If necessary, additional instance variables and methods could be added to the classes BT<T> and Node<T> (explanation should be provided for these extra resources).
The interface BTinterface<T> specifies the following methods that will be implemented by the class BT<T> using recursive techniques:
- inorder, preorder, postorder for tree traversal - these methods should return the corresponding string representation of the tree;
- insertLeftChild, insertRightChild - these methods take the value of the new node and the value of its parent node as parameters and return a reference to the new inserted node.
- isMember - takes the value as parameter and returns the reference to the node containing the specified value or null is the value is not in the tree.
- isLeaf - takes the value as parameter and returns true the node containing that value is a tree leaf and null otherwise.
- getMaxLevels - returns the maximum number of tree levels.
- getNumberOfNodesAtLevel - returns the number of nodes located at a specified level;
- getTotalNumberOfTreeNodes
Part 2 – Representing and processing ancestors
The generic BT class developed in Part 1 will be used as the main data structure for an application of representing and processing personal ancestors.
A binary tree can be represented as an array. At the same time, an array can be represented as a binary tree. For converting an array into a binary tree and vice versa, a level by level approach should be employed. Below is an example showing the binary tree of all known ancestors of john and its array equivalent representation where empty spaces are represented as null values.
2.1 Consider an input text file ancestors.txt representing the values of an array of strings. The strings in the file are separated by a semicolon. Read the textfile and build a corresponding binary tree object. For example the ancestors of john illustrated above will be represented in the input file as:
john;mary;tim;lily;luke;anna;nick;null;null;helen;null;null;bill;null;null;null;
Important note. The ancestors’ names should be unique. In real situations this requirement could be fulfilled by considering the name of the person together with their birth date. For simplicity, in this project we will consider that the person names are unique.
2.2 After building the binary tree object, in a loop, the program should invite the user to select for execution one of the following operations: (1) inorder, (2) preorder, (3) postorder, (4) getMaxLevels, (5) getNumberOfNodesAtLevel, (6) getTotalNumberOfNodes, (7) isMember, (8) isLeaf, (9) insertLeftChild, (10) insertRightChild and (0) exit the loop and the program.
As a result of each operation execution, relevant information should be displayed to the user. For example, as a result of invoking inorder operation method, the tree node values should be displayed.
The programs should compile without errors.
Notes.
1. If an operation requires additional information, the user will be prompted to enter it.
2. The input file ancestors.txt should be generated by the students using a simple text editor such as Notepad.
3. You may assume that there are no errors in the input file.
4. Tree root is considered as located at level 0. Tree height will be considered by counting the nodes, starting with the root, along the longest path.
Explanation / Answer
using ConsoleApplication1;
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinaryTree
{
public class BTnode<T> : Node<T>
{
Node<T> root;
public BTnode() : base() { }
public BTnode(T data) : base(data, null) { }
public BTnode(T data, BTnode<T> left, BTnode<T> right)
{
base.Value = data;
NodeList<T> children = new NodeList<T>(2);
children[0] = left;
children[1] = right;
base.Neighbors = children;
}
public BTnode<T> Left
{
get
{
if (base.Neighbors == null)
return null;
else
return (BTnode<T>)base.Neighbors[0];
}
set
{
if (base.Neighbors == null)
base.Neighbors = new NodeList<T>(2);
base.Neighbors[0] = value;
}
}
public BTnode<T> Right
{
get
{
if (base.Neighbors == null)
return null;
else
return (BTnode<T>)base.Neighbors[1];
}
set
{
if (base.Neighbors == null)
base.Neighbors = new NodeList<T>(2);
base.Neighbors[1] = value;
}
}
}
public class BT<T> : BTinterface
{
private BTnode<T> root;
public BT()
{
root = null;
}
public virtual void Clear()
{
root = null;
}
public BTnode<T> Root
{
get
{
return root;
}
set
{
root = value;
}
}
public void inorder(BTnode<T> root)
{
if (root != null)
{
inorder(root.Left);
inorder(root.Right);
}
}
public void Preorder(BTnode<T> root)
{
if (root != null)
{
Preorder(root.Left);
Preorder(root.Right);
}
}
public void postorde(BTnode<T> root)
{
if (root != null)
{
postorde(root.Left);
postorde(root.Right);
}
}
public void insertLeftChild(Node<T> _root)
{
if (root.Left != null)
{
root.insertLeftChild(_root.Value);
}
else
{
root.Left = new BTnode<T>(_root);
}
}
public void insertRightChild(Node<T> _root)
{
if (root.Left != null)
{
root.insertRightChild(_root.Value);
}
else
{
root.Left = new BTnode<T>(_root);
}
}
}
interface BTinterface<T>
{
void inorder(BTnode<T> root);
void preorder(BTnode<T> root);
void postorde(BTnode<T> root);
void insertLeftChild (BTnode<T> root);
void insertRightChild (BTnode<T> root);
Boolean isMember ();
Boolean isLeaf ();
int getMaxLevels ();
BTnode<T> getNumberOfNodesAtLevel ();
BTnode<T> getTotalNumberOfTreeNodes();
}
public class Node<T>
{
// Private member-variables
private T data;
private NodeList<T> neighbors = null;
public Node() { }
public Node(T data) : this(data, null) { }
public Node(T data, NodeList<T> neighbors)
{
this.data = data;
this.neighbors = neighbors;
}
public T Value
{
get
{
return data;
}
set
{
data = value;
}
}
protected NodeList<T> Neighbors
{
get
{
return neighbors;
}
set
{
neighbors = value;
}
}
}
public class NodeList<T> : Collection<Node<T>>
{
public NodeList() : base() { }
public NodeList(int initialSize)
{
// Add the specified number of items
for (int i = 0; i < initialSize; i++)
base.Items.Add(default(Node<T>));
}
public Node<T> FindByValue(T value)
{
// search the list for the value
foreach (Node<T> node in Items)
if (node.Value.Equals(value))
return node;
// if we reached here, we didn't find a matching node
return null;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinaryTree
{
class Program
{
static void Main(string[] args)
{
BT<int> btree = new BT<int>();
btree.Root = new BTnode<int>(1);
btree.Root.Left = new BTnode<int>(2);
btree.Root.Right = new BTnode<int>(3);
btree.Root.Left.Left = new BTnode<int>(4);
btree.Root.Right.Right = new BTnode<int>(5);
btree.Root.Left.Left.Right = new BTnode<int>(6);
btree.Root.Right.Right.Right = new BTnode<int>(7);
btree.Root.Right.Right.Right.Right = new BTnode<int>(8);
}
}
}