Question

Add a public method called CountChildren to the OurPriorityQueue class that receives a priority value and returns the number of children nodes below the node with the priority value. It must call a private recursive method that does the actual counting of children nodes.

The recursive private method must count and return the number of nodes within a subtree where the subtree’s “root” node has a Value that equals the value passed into the method. Do not include the parent node in your count. Do not add any variable(s) to the class.

Example:

Empty Tree ==> Count children(1) =-1

                  1
       ┌───┴───┐
     2       3
   ┌─┴─┐        ┌─┘
   4         5        6

---------------
Count children(1) returns 5
Count children(2) returns 2
Count children(3) returns 1
Count children(4) returns 0

OURPRIORITYQUEUE CLASS

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
///

/// A Priority Queue with a lower value is a higher priority
///

///
///
public class OurPriorityQueue where TPriority : IComparable
{
///
/// Private class for each cell in the array
///
private class Cell
{
///
/// The data - this can be any data type not just an int or string
///
public TValue Value { get; set; }
///
/// The priority value for the data, it can be any data type as long as the type it comparable
///
public TPriority Priority { get; set; }

public Cell(TPriority aPriority = default(TPriority), TValue aValue = default(TValue))
{
Priority = aPriority;
Value = aValue;
}
public override string ToString()
{
return Priority + ":" + Value;
}
}
// -------------------------------------------------------

///

/// The array where each cell is initially null
///
private Cell[] table;   
///
/// Keeps track of the number of items
///
private int count = 0;

public OurPriorityQueue(int size = 100)
{
if (size < 10)
size = 10;

table = new Cell[size];
}
///

/// Returns true is there are no items stored
///
///
public bool IsEmpty()
{
return count == 0;
}

///

/// Changes the count to 0 but doesn't change any of the cells, the old data will be overridden later
///
public void Clear()
{
count = 0;
}

///

/// Returns the data at the root but does not remove it
///
///
public TValue Peek()
{
if (IsEmpty() == true)
throw new ApplicationException("Can't Peek an empty OurPriorityQueue");

return table[1].Value;
}

///

/// Adds a new item using its priority to help place it in the array
///
///
///
public void Add(TPriority aPriority, TValue aValue)
{
if (isFull() == true)
return;

// Percolate up
int hole = ++count; // the hold goes on the bottom level
// keep moving the hold up until it is the root or the hole's parent has a lower priority
for (; hole > 1 && aPriority.CompareTo(table[hole / 2].Priority) < 0; hole /= 2)
table[hole] = table[hole / 2];
// put the priority, value pair in the array where the hole is
table[hole] = new Cell(aPriority, aValue);
}

///

/// Remove and return the highest priority data
///
///
public TValue Remove()
{
if (IsEmpty() == true)
throw new ApplicationException("Can't Remove from an empty OurPriorityQueue");

// save the data for later
TValue value = table[1].Value;
// put the last item in the tree in the root
table[1] = table[count--];

// keep moving the lowest child up until we've found the right spot
// for the item moved from the last level to the root
percolateDown(1);

return value;
}

///

/// Reposition the hole down until it is in the right spot for its priority
///
///
private void percolateDown(int hole)
{
int child;
// save the hole's cell in a tmp spot
Cell pTmp = table[hole];

// keep going down the tree until the last level
for (; hole * 2 <= count; hole = child)
{
child = hole * 2; // get right child
// check right and left child and put lowest one in the child variable
if (child != count && table[child + 1].Priority.CompareTo(table[child].Priority) < 0)
child++;
// put lowest child in hole
if (table[child].Priority.CompareTo(pTmp.Priority) < 0)
table[hole] = table[child];
else
break;
}
// found right spot of hole's original value, put it back into tree
table[hole] = pTmp;
}
///

/// Assumes all but last item in array is in correct order
/// Shifts last item in array into correct location based on priority
///
public void buildHeap()
{
for (int i = count / 2; i > 0; i--)
percolateDown(i);
}

// return contents of array in order (e.g. left child, parent, right child)
public StringBuilder InOrder()
{
return InOrder(1);
}
private StringBuilder InOrder(int position) // why?? What does this do??
{
StringBuilder str = new StringBuilder();
if (position <= count)
{
str.Append(InOrder(position * 2) + "\t");
str.Append(table[position].Value.ToString() + "\n ");
str.Append(InOrder(position * 2 + 1) + "\t");
//str.Append("\t" + InOrder(position * 2) + " ");
//str.Append("\n" + mTable[position].Value.ToString() + " ");
//str.Append("\t" + InOrder(position * 2 + 1) + " ");
}
return str;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = 1; i < count; i++)
{
sb.Append(table[i].Value.ToString() + "; ");
}
return sb.ToString();
}
}
}

Answer 1

After looking the Add and remove function we can understand that the table array is built in a order of highest priority to the lowest priority. So the root node is of higest priority. However we can visualise it as simple binary tree implemented in a array.

The following code serves the purpose of the question

//This is the recursive function returns the number of child in a given index

private int child_total(int i){  //if the parent had child
if(i<=count || table[i].Value!= NULL){

return child_total(2*i) + child_total(2*i + 1) + 1; //recurse on left and right child and add 1 to keep the count

}
else //if the index is not out of bound, which means the parent had no child
return 0;
}

public void CountChildren(TValue aValue, ref int counter_child)
{
int i;
int total_child=0;
for(i=1; i<count; i++){ //find the index of the key
if(table[i].Value== aValue){
break;
}
}
if(i==count){ //if key was not found it will return 0
Console.WriteLine(total_child);
}
else{ //if the key was found call the recursive function
total_child=child_total(int i);
}  
}