Question
Can someone please tell me why I keep getting the following error when I compile this program? Error message on running code: Project4BinaryTree.java:1: '{' expected public class BinaryTree where T : IComparable Project4BinaryTree.java:2: illegal start of type public class BinaryTree where T : IComparable{ private BinaryTreeNode root; public int Count; public void Insert(T value) { BinaryTreeNode node = new BinaryTreeNode(value); Insert(node); } public void Insert(BinaryTreeNode node) { if (node == null) { throw new ArgumentNullException("node","node cannot be null"); } if (root == null) { root = node; } else { Insert(node, ref root); } Count++; } public void Delete(T value, bool rebalanceTree) { BinaryTreeNode parentNode; BinaryTreeNode foundNode = null; BinaryTreeNode tree = parentNode = root; //Search for the node while keeping a reference to the parent while (tree != null) { if (value.CompareTo(tree.Data) == 0) { foundNode = tree; break; } else if (value.CompareTo(tree.Data) < 0) { parentNode = tree; tree = tree.Left; } else if (value.CompareTo(tree.Data) > 0) { parentNode = tree; tree = tree.Right; } } if (foundNode == null) { throw new Exception("Node not found in binary tree"); } bool leftOrRightNode = false; if (foundNode != parentNode.Left) { leftOrRightNode = true; } if (foundNode == parentNode) //oh oh. We're trying to delete the root here. { if (rebalanceTree) { //Let's just remove the parent and rebalance the tree //to ensure our tree will be nice and balanced //after the removal IList> listOfNodes = new List>(); FillListInOrder(root, listOfNodes); RemoveChildren(listOfNodes); listOfNodes.Remove(parentNode); root = null; int count = Count - 1; Count = 0; BalanceTree(0, count - 1, listOfNodes); } else { //Regular way without balancing: just find the left-most node on the right //side of the tree and that will become the root BinaryTreeNode leftMost = FindLeftMost(parentNode.Right, true); if (leftMost != null) { leftMost.Left = parentNode.Left; leftMost.Right = parentNode.Right; root = leftMost; } } } else if (foundNode.Left == null && foundNode.Right == null) //This is a leaf node { //Just set it to null if (leftOrRightNode) { parentNode.Right = null; } else { parentNode.Left = null; } } else if (foundNode.Left != null && foundNode.Right != null) //This is a node with two children { if (leftOrRightNode) { parentNode.Right = foundNode.Right; parentNode.Right.Left = foundNode.Left; } else { parentNode.Left = foundNode.Right; parentNode.Left.Left = foundNode.Left; } } else if (foundNode.Left != null || foundNode.Right != null) //This is a node with a single child { if (foundNode.Left != null) { if (leftOrRightNode) { parentNode.Right = foundNode.Left; } else { parentNode.Left = foundNode.Left; } } else { if (leftOrRightNode) { parentNode.Right = foundNode.Right; } else { parentNode.Left = foundNode.Right; } } } } public BinaryTreeNode Search(T value) { BinaryTreeNode tree = root; while (root != null) { if (value.CompareTo(tree.Data) == 0) { return tree; } else if (value.CompareTo(tree.Data) < 0) { tree = tree.Left; } else if (value.CompareTo(tree.Data) > 0) { tree = tree.Right; } } return null; } public IEnumerable> InOrder() { return InOrder(root); } private IEnumerable> InOrder(BinaryTreeNode node) { if (node != null) { foreach(BinaryTreeNode left in InOrder(node.Left)) { yield return left; } yield return node; foreach (BinaryTreeNode right in InOrder(node.Right)) { yield return right; } } } public IEnumerable> PreOrder() { return PreOrder(root); } public IEnumerable> PostOrder() { return PostOrder(root); } public IEnumerable> BreadthFirstTraversal() { Queue> queue = new Queue>(); queue.Enqueue(root); while (queue.Count != 0) { BinaryTreeNode current = queue.Dequeue(); if (current != null) { queue.Enqueue(current.Left); queue.Enqueue(current.Right); yield return current; } } } public IEnumerable> DepthFirstTraversal() { Stack> queue = new Stack>(); BinaryTreeNode current; queue.Push(root); while (queue.Count != 0) { current = queue.Pop(); if (current != null) { queue.Push(current.Right); queue.Push(current.Left); yield return current; } } } public void BalanceTree() { IList> listOfNodes = new List>(); FillListInOrder(root, listOfNodes); RemoveChildren(listOfNodes); root = null; int count = Count; Count = 0; BalanceTree(0, count - 1, listOfNodes); } private void Insert(BinaryTreeNode node, ref BinaryTreeNode parent) { if (parent == null) { parent = node; } else { if (node.Data.CompareTo(parent.Data) < 0) { Insert(node, ref parent.Left); } else if (node.Data.CompareTo(parent.Data) > 0) { Insert(node, ref parent.Right); } else if (node.Data.CompareTo(parent.Data) == 0) { throw new ArgumentException("Duplicate node"); } } } private void BalanceTree(int min, int max, IList> list) { if (min <= max) { int middleNode = (int)Math.Ceiling(((double)min + max) / 2); Insert(list[middleNode]); BalanceTree(min, middleNode - 1, list); BalanceTree(middleNode + 1, max, list); } } private void FillListInOrder(BinaryTreeNode node, ICollection> list) { if (node != null) { FillListInOrder(node.Left, list); list.Add(node); FillListInOrder(node.Right, list); } } private void RemoveChildren(IEnumerable> list) { foreach(BinaryTreeNode node in list) { node.Left = null; node.Right = null; } } private IEnumerable> PreOrder(BinaryTreeNode node) { if (node != null) { yield return node; foreach (BinaryTreeNode left in PreOrder(node.Left)) { yield return left; } foreach (BinaryTreeNode right in PreOrder(node.Right)) { yield return right; } } } private IEnumerable> PostOrder(BinaryTreeNode node) { if (node != null) { foreach (BinaryTreeNode left in PostOrder(node.Left)) { yield return left; } foreach (BinaryTreeNode right in PostOrder(node.Right)) { yield return right; } yield return node; } } private BinaryTreeNode FindLeftMost(BinaryTreeNode node, bool setParentToNull) { BinaryTreeNode leftMost = null; BinaryTreeNode current = leftMost = node; BinaryTreeNode parent = null; while (current != null) { if (current.Left!=null) { parent = current; leftMost = current.Left; } current = current.Left; } if (parent!=null && setParentToNull) { parent.Left = null; } return leftMost; } } [Serializable] public class BinaryTreeNode where T : IComparable{ public BinaryTreeNode(T value) { Data = value; } public T Data { get; set; } public BinaryTreeNode Left; public BinaryTreeNode Right; }
Explanation / Answer
#include "stdafx.h" #include #include #include #include "GenericNodeClass.h" using namespace std; using namespace System; using namespace System::Collections; using namespace System::Collections::Generic; generic where T : IComparable , IEquatable ref class BinarySearchTreeClass { public: Node^ rootNode; T _p; // constructors // default BinarySearchTreeClass(){} BinarySearchTreeClass(T t) { // create a new Node in the Binary Search Tree rootNode = gcnew Node (t); } // method to return a node if it exists in the tree // takes two parameters: an instance of the Node class, and a // value representing the value of the node to be looked up Node ^ lookUp(Node ^node, T key) { if(node == nullptr) return node; if(node->data == key) return node; else { if (node->data->CompareTo(key) < 0) return lookUp(node->right, key); else return lookUp(node->left, key); } } // method to create new node. Method takes two parameters: // a parameter of the value for the node data, and a value // for the node's parent. Node ^newNode(T key, T parent) { Node ^node = gcnew Node(key); node->data = key; node->left = nullptr; node->right = nullptr; node->parent = parent; return node; } // insertNode method inserts a new node into an existing // Binary Search Tree. This method takes two parameters: // an instance of Node (node), and a value of T, // representing the value of the node being inserted Node ^insertNode(Node ^node, T input) { Node ^returnNode; if (node != nullptr) _p = node->data; // if the node is non-existant, create a new node // with the value of the parameter 'input' and the // value of the new node's parent (_p). if (node == nullptr) { // pass class variable _p to set value // of the new node's parent value. returnNode = newNode(input, _p); return returnNode; } // if the input parameter value is less than // or equal to the node value, insert node using // the left hand node leaf of the current node // as starting point if (input->CompareTo(node->data) < 0) { // set variable p to value of node->data value (this // will be the parent of the new node) _p = node->data; node->left = insertNode(node->left, input); } // if the input parameter value is greater than // the node value, insert node using the right hand // node leaf of the current node as starting point else { _p = node->data; node->right = insertNode(node->right, input); } return node; } // method to find the left most node in a Binary Search Tree // takes an instance of Node as parameter Node ^leftMost(Node ^node) { if (node == nullptr) return nullptr; while (node->left != nullptr) node = leftMost(node->left); return node; } // method of return the right most node in a Binary Search Tree // takes an instance of Node as parameter Node ^rightMost(Node ^node) { if (node == nullptr) return nullptr; while (node->right != nullptr) node = rightMost(node->right); return node; } // method to return the size of a Binary Tree // takes an instance of Node as parameter int treeSize(Node ^node) { if(node == nullptr || node->left == nullptr && node->right == nullptr) return 0; else return treeSize(node->left) + 1 + treeSize(node->right); } // method that prints to console the value of each node from lowest to highest // takes an instance of Node as parameter void printTreeInOrder(Node ^node) { if (node != nullptr) { printTreeInOrder(node->left); Console::WriteLine(node->data); printTreeInOrder(node->right); } } // method that prints to console a graphic representation of a binary tree // takes an instance of Node as parameter void printGraphicRepresentation(Node ^node) { // the width of the tree is the max height /2 (?) // need to know how wide the tree is // At treeWidth / 2, print node // on new line, at nodePosition - 1, if node has a left, print a "/" // on same line, at nodePosition + 1, if node has a right, print a "" } // method that prints to console all members of a given node // takes an instance of Node as parameter void printNodeMembers(Node ^node) { Console::WriteLine("Members of Node " + node->data + " include: "); if (node->parent != nullptr) Console::WriteLine("Parent: " + node->parent); else Console::WriteLine("This node has no parent."); if (node->left != nullptr) Console::WriteLine("Left-member: " + node->left->data); else Console::WriteLine("This node has no left-member."); if (node->right != nullptr) Console::WriteLine("Right-Member: " + node->right->data); else Console::WriteLine("This node has no right-member."); } };