Language C++: implement a doubly linked list class, then: Implement a tree class

Question

Language C++:

implement a doubly linked list class,

then:

Implement a tree class based on the implementation

- you can choose either (1) use nodes to make a tree structure or (2) make a tree class based on linked lists to look like trees.

Additional functions for the tree class

- overloaded operator "=="

- traversal function

- use the quick sort code

AGAIN PLEASE DO NOT POST SOURCE CODE ON HERE...SEND IT TO GOOGLE ACCOUNT astudent969....IF YOU ARE NOT COMFORTABLE WITH THE EMAIL YOU DO NOT HAVE TO ANSWER POST

#include
using namespace std;

void swap(int &a, int &b);
int partition (int arr[], int low, int high);
void quickSort(int arr[], int low, int high);
void printArray(int arr[], int size);

void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}

int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}


void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<

Explanation / Answer

DLL to BST function

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

private static DoubleLinkedListNode convertDLLToBST(int start, int end){
if( start > end)
return null;
int mid = (start+end) / 2;
DoubleLinkedListNode nodeLeft = convertDLLToBST( start, mid-1);
currentNode.previous = nodeLeft;
DoubleLinkedListNode thisNode = currentNode;
currentNode = currentNode.next;
DoubleLinkedListNode nodeRight = convertDLLToBST( mid+1 , end);
thisNode.next = nodeRight;
return thisNode;

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.