C++: Implement a doubly linked list class, then: Implement a tree class based on
ID: 3831763 • Letter: C
Question
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 below
--quicksort code--
#include <iostream>
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);
// A utility function to swap two elements
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
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);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
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);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = 6;
quickSort(arr, 0, n-1);
cout<<"Sorted array: ";
printArray(arr, n);
return 0;
}
Explanation / Answer
*****************************************************************************************************
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct ListNode
{
int data;
ListNode* next;
};
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left, *right;
};
void push(struct ListNode** head_ref, int new_data)
{
struct ListNode* new_node = new ListNode;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
BinaryTreeNode* newBinaryTreeNode(int data)
{
BinaryTreeNode *temp = new BinaryTreeNode;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void convertList2Binary(ListNode *head, BinaryTreeNode* &root)
{
queue<BinaryTreeNode *> q;
if (head == NULL)
{
root = NULL;
return;
}
root = newBinaryTreeNode(head->data);
q.push(root);
head = head->next;
while (head)
{
BinaryTreeNode* parent = q.front();
q.pop();
BinaryTreeNode *leftChild = NULL, *rightChild = NULL;
leftChild = newBinaryTreeNode(head->data);
q.push(leftChild);
head = head->next;
if (head)
{
rightChild = newBinaryTreeNode(head->data);
q.push(rightChild);
head = head->next;
}
parent->left = leftChild;
parent->right = rightChild;
}
}
void inorderTraversal(BinaryTreeNode* root)
{
if (root)
{
inorderTraversal( root->left );
cout << root->data << " ";
inorderTraversal( root->right );
}
}
int main()
{
struct ListNode* head = NULL;
push(&head, 36);
push(&head, 30);
push(&head, 25);
push(&head, 15);
push(&head, 12);
push(&head, 10);
BinaryTreeNode *root;
convertList2Binary(head, root);
cout << "Inorder Traversal of the constructed Binary Tree is: ";
inorderTraversal(root);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.