Use Binary Trees.. Write a tree for strings with pointers in C++, and test it by

Question

Use Binary Trees.. Write a tree for strings with pointers in C++, and test it by creating a DRIVER/Test class with int main. Use your class in it to test that they are working.

Explanation / Answer

#include #include #include using namespace std; // Linked list node struct ListNode { int data; ListNode* next; }; // Binary tree node structure struct BinaryTreeNode { int data; BinaryTreeNode *left, *right; }; // Function to insert a node at the beginning of the Linked List void push(struct ListNode** head_ref, int new_data) { // allocate node and assign data struct ListNode* new_node = new ListNode; new_node->data = new_data; // link the old list off the new node new_node->next = (*head_ref); // move the head to point to the new node (*head_ref) = new_node; } // method to create a new binary tree node from the given data BinaryTreeNode* newBinaryTreeNode(int data) { BinaryTreeNode *temp = new BinaryTreeNode; temp->data = data; temp->left = temp->right = NULL; return temp; } // converts a given linked list representing a complete binary tree into the // linked representation of binary tree. void convertList2Binary(ListNode *head, BinaryTreeNode* &root) { // queue to store the parent nodes queue q; // Base Case if (head == NULL) { root = NULL; // Note that root is passed by reference return; } // 1.) The first node is always the root node, and add it to the queue root = newBinaryTreeNode(head->data); q.push(root); // advance the pointer to the next node head = head->next; // until the end of linked list is reached, do the following steps while (head) { // 2.a) take the parent node from the q and remove it from q BinaryTreeNode* parent = q.front(); q.pop(); // 2.c) take next two nodes from the linked list. We will add // them as children of the current parent node in step 2.b. Push them // into the queue so that they will be parents to the future nodes 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; } // 2.b) assign the left and right children of parent parent->left = leftChild; parent->right = rightChild; } } // Utility function to traverse the binary tree after conversion void inorderTraversal(BinaryTreeNode* root) { if (root) { inorderTraversal( root->left ); cout

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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