The Computer Science Department would like to decide which courses to offer for
ID: 3633559 • Letter: T
Question
The Computer Science Department would like to decide which courses to offer for the next semester and would like to offer only the courses that are in demand by the students. Write a program to allow the students to input the courses that they would like to take the next semester. The first time a course is submitted by a student, the course comes into existence and a counter for the course is set to 1 (showing that one student is interesting in taking the course). If the course already exists and a student would like for the course to be offered, the counter for the course is incremented. Display the course numbers (from smallest to largest) with corresponding counters. Remove the courses with only one student interested in taking the course. Display the course numbers (from smallest to largest) with corresponding counters after courses with one interested student have been deleted.Programming Guidelines:
- Use a binary search tree to store the information on the courses.
- Use the appropriate binary tree traversal that will give you the correct output.
There are several ways to deal with the fact that the node will store the course number as well as a counter.
The following definition for the binary search tree modifies the node class to hold the two values:
class node
{
friend class BinarySearchTree;
private:
int courseNumber;
int counter;
node * leftchild;
node * rightchild;
};
class BinarySearchTree
{
public:
BinarySearchTree();
bool empty(); // return true if the tree is empty, otherwise return false
bool Insert(int courseNum);//insert a value x
bool IsThere (int courseNum);
//return true if x is in the tree, otherwise return false
void Delete(int courseNum); //if value x is in the tree, remove x
void Display();// Display the data values stored from smallest to largest
private:
node * root;//pointer to the roor node
};
The following definition for the binary search tree using a struct to hold the two values:
struct course{
int courseNumber;
int counter;
};
typedef course ElementType;
class node
{
friend class BinarySearchTree;
private:
ElementType data;
node * leftchild;
node * rightchild;
};
class BinarySearchTree
{
public:
BinarySearchTree();
bool empty(); // return true if the tree is empty, otherwise return false
bool Insert(ElementType x);//insert a value x
bool IsThere (ElementType x);
//return true if x is in the tree, otherwise return false
void Delete(ElementType x); //if value x is in the tree, remove x
void Display();// Display the data values stored from smallest to largest
private:
node * root;//pointer to the roor node
};
Sample input:
285
280
163
165
476
365
163
280
280
165
365
365
165
280
476
163
163
385
Sample output:
List of all courses:
163 – 4
165 – 3
280 – 4
285 – 1
365 – 3
385 – 1
476 – 2
List of courses more than one student interested:
163 – 4
165 – 3
280 – 4
365 – 3
476 – 2
Explanation / Answer
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. Binary trees are used to implement binary search trees and binary heaps. Definitions for r trees A directed edge refers to the link from the parent to the child (the arrows in the picture of the tree). The root node of a tree is the node with no parents. There is at most one root node in a rooted tree. A leaf node has no children. The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero. The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero. Siblings are nodes that share the same parent node. A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p. The size of a node is the number of descendants it has including itself. In-degree of a node is the number of edges arriving at that node. Out-degree of a node is the number of edges leaving that node. The root is the only node in the tree with In-degree = 0. [edit]Types of binary trees A rooted binary tree is a tree with a root node in which every node has at most two children. A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children. A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.[1] (This is ambiguously also called a complete binary tree.) A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.[2] An infinite complete binary tree is a tree with a countably infinite number of levels, in which every node has two children, so that there are 2d nodes at level d. The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable: it has the cardinality of the continuum. These paths corresponding by an order preserving bijection to the points of the Cantor set, or (through the example of the Stern–Brocot tree) to the set of positive irrational numbers. A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1.,[3] although in general it is a binary tree where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther" [4]). Binary trees that are balanced according to this definition have a predictable depth (how many nodes are traversed from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ..., depth). This depth is equal to the integer part of log2(n) where n is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). Example 3: balanced tree with 5 nodes, log2(5) = 2.32 (depth of tree is 2 nodes). A rooted complete binary tree can be identified with a free magma. A degenerate tree is a tree where for each parent node, there is only one associated child node. This means that in a performance measurement, the tree will behave like a Linked list data structure. Note that this terminology often varies in the literature, especially with respect to the meaning "complete" and "full". [edit]Properties of binary trees The number of nodes n in a perfect binary tree can be found using this formula: n = 2h + 1 - 1 where h is the height of the tree. The number of nodes n in a complete binary tree is at least n = 2h and at most n = 2h + 1 - 1 where h is the height of the tree. The number of leaf nodes L in a perfect binary tree can be found using this formula: L = 2h where h is the height of the tree. The number of nodes n in a perfect binary tree can also be found using this formula: n = 2L - 1 where L is the number of leaf nodes in the tree. The number of null links (absent children of nodes) in a complete binary tree of n nodes is (n+1). The number of internal nodes in a Complete Binary Tree of n nodes is . For any non-empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1.[5] Proof: Let n = the total number of nodes B = number of branches n0, n1, n2 represent the number of nodes with no children, a single child, and two children respectively. B = n - 1 (since all nodes except the root node come from a single branch) B = n1 + 2*n2 n = n1+ 2*n2 + 1 n = n0 + n1 + n2 n1+ 2*n2 + 1 = n0 + n1 + n2 ==> n0 = n2 + 1 [edit]Common operations There are a variety of different operations that can be performed on binary trees. Some are mutator operations, while others simply return useful information about the tree. [edit]Insertion Nodes can be inserted into binary trees in between two other nodes or added after an external node. In binary trees, a node that is inserted is specified as to which child it is. [edit]External nodes Say that the external node being added on to is node A. To add a new node after node A, A assigns the new node as one of its children and the new node assigns node A as its parent. [edit]Internal nodes The process of inserting a node into a binary tree Insertion on internal nodes is slightly more complex than on external nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion.) A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node. [edit]Deletion Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.[6] [edit]Node with zero or one children The process of deleting an internal node in a binary tree Say that the node to delete is node A. If a node has no children (external node), deletion is accomplished by setting the child of A's parent to null. If it has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child. [edit]Node with two children In a binary tree, a node with two children cannot be deleted unambiguously.[6] However, in certain binary trees these nodes can be deleted, including binary search trees. [edit]Iteration Often, one wishes to visit each of the nodes in a tree and examine the value there, a process called iteration or enumeration. There are several common orders in which the nodes can be visited, and each has useful properties that are exploited in algorithms based on binary trees: Pre-Order: Root first, Left child, Right child Post-Order: Left Child, Right child, root In-Order: Left child, root, right child.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.