In this assignment you will be given a C++ implementation of the general tree no
ID: 3598893 • Letter: I
Question
In this assignment you will be given a C++ implementation of the general tree node ADT and the general tree ADT that was introduced in class. Add the needed implementation to do the following [4 points] Write a function to determine if two general trees are identical. The input should be two general trees and the output should be True/False to indicate whether theses trees are identical or not [6 points] Write a function that returns the sequential representation for general trees using the coding illustrated by Example 6.8 (page 222). The input should be a pointer to the root of a general tree and the output should be the resulting sequential representation of that general [6 points] Write a function to decode the sequential representation for general trees tree illustrated by Example 6.8 (page 222). The input should be the sequential representation and the output should be a pointer to the root of the resulting general tree [Optional: 3 points] Using the general tree ADT, write a function that takes as input the root of a general tree and returns a root of a binary tree generated by the conversion process illustrated by Figure 6.15 in page 219. Each node points to two children in a new binary tree The left child of this new structure is the node's first child in the general tree. The right child is the node's right sibling 1. 2. 3. 4. 5. In the main function do the following: a. [2.5 point] Create the general tree shown in Figure T. [0.5 point] Display the sequential representation of the general tree using the function you designed in b. c. [1 point] Check whether the sequential representation generated in (b) will be decoded to the original tree created in (a). Note: you should use the functions you designed in (1) and (3) 0 d. [Optional: 0.5 point] Convert the general tree to binary tree using the function you designed in (4) Figure 1: Sample treeExplanation / Answer
/* For question 4 : please mention that how to convert sequential tree to binary tree.
// in the question it is not mention that, how to convert sequential tree to binary tree...for example if general tree has //more than 4 or 5 child then how to adjust binary tree length.*/
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
/* A tree node has data, pointer to first child
and a pointer to second child ... you can add as many child as you want*/
struct node
{
int data;
struct node* first;// 1st child
struct node* second; // 2nd child
struct node* third; // 3rd child
// add as many child
};
/* Helper function that allocates a new node with the
given data and NULL first and second pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->first = NULL;
node->second = NULL;
node->third = NULL;
return(node);
}
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
if (a!=NULL && b!=NULL)
{
return
(
// if you add any more child just call the function identicalTrees with that child
// for example if you have fourth child just add the identicalTrees(a->fourth, b->fourth)
a->data == b->data &&
identicalTrees(a->first, b->first) &&
identicalTrees(a->second, b->second) && identicalTrees(a->third, b->third)
);
}
/* 3. one empty, one not -> false */
return 0;
}
std::vector<int> myvector;
std::stack<int> mystack;
// In the below code if root is null return other wise
// add the root data to the vector and recursively call the same function with first sub tree and then second sub tree
// once the function is completed just print the vector it contain sequential represtation tree.
// in the code, i have consider only 3 child but you can create as many child
void sequentialRepresentaion(struct node *root){
if(root ==NULL)
return ;
else{
myvector.push_back(root->data);
sequentialRepresentaion(root->first);
sequentialRepresentaion(root->second);
sequentialRepresentaion(root->third);
}
}
// 3rd question
// the first node is the root node in sequential represtation
int returnRootNode(std::vector<int> myvector){
if(myvector.begin() != myvector.end())
return myvector[0];
}
/* Driver program to test identicalTrees function*/
int main()
{
struct node *root1 = newNode(1);
struct node *root2 = newNode(1);
root1->first = newNode(2);
root1->second = newNode(3);
root1->first->first = newNode(4);
root1->first->second = newNode(5);
root2->first = newNode(2);
root2->second = newNode(3);
root2->first->first = newNode(4);
root2->first->second = newNode(5);
if(identicalTrees(root1, root2))
cout<<"Both tree are identical."<<endl;
else
cout<<"Trees are not identical."<<endl;
sequentialRepresentaion(root1);
for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
std::cout << ' ' << *it;
cout<<endl;
cout<<"Root Node :"<<returnRootNode(myvector)<<endl;
getchar();
return 0;
}