To implement the Binary tree ADT using a linked structure with C/C++. We further
ID: 3576292 • Letter: T
Question
To implement the Binary tree ADT using a linked structure with C/C++. We further define the balance factor of a binary tree as the difference in height between its left and right subtrees. Your main program should be named as HW5 and should read a text file, binaryTree .txt, which contains the information of the input binary tree. The input text file format is as follow In the text file, each line indicates a relation between parent and children. For example, the first line says that root r has two children n_11 and n_12. The third line indicates that node n_12 has only one child n_23. Note that, the last digit in the name of a node denotes that it is a left child or a right child. If the last digit of a node v is even, then node v is a right child of its parent; otherwise, it is a left child. After reading the text file, your program should be able to present the input tree using linked structure. Then, the program performs the preorder, inorder, and postorder of the binary tree as well as computes the balance factor of the tree. Below shows the execution example. Suppose the input text file contains the above lines.Explanation / Answer
Solution: See the code below
-------------------------------
/**
* Program to create a binary tree and show its traversals and balance factor
*/
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <sstream>
using namespace std;
//node definition of binary tree
struct TreeNode {
string item; //data item
TreeNode *left; //reference to left child
TreeNode *right; //reference to right child
};
//root of tree
TreeNode *root = NULL; //initially tree will be empty
//preorder traversal
void preorder(TreeNode* root) {
if (root != NULL) {
cout << root->item << " ";
preorder(root->left);
preorder(root->right);
}
}
//postorder traversal
void postorder(TreeNode* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->item << " ";
}
}
//inorder traversal
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left);
cout << root->item << " ";
inorder(root->right);
}
}
//gets height of tree
int get_height(TreeNode* root) {
if (root != NULL) {
int left_tree_height = get_height(root->left);
int right_tree_height = get_height(root->right);
if (left_tree_height > right_tree_height)
return (left_tree_height + 1);
else
return (right_tree_height + 1);
} else
return 0;
}
//search an item
TreeNode* search(TreeNode *root, string key) {
if (root != NULL) {
int keyLastDigit = key.at(key.length() - 1) - '0';
if (key.compare(root->item) == 0) {
return root;
} else if (keyLastDigit % 2 != 0) {
return search(root->left, key);
} else if (keyLastDigit % 2 == 0) {
return search(root->right, key);
}
}
return root;
}
//insert an item
void insert_item(string key) {
TreeNode *p = root, *parent = NULL;
if (root == NULL) //is empty
{
root = new TreeNode;
root->item = key;
root->left = NULL;
root->right = NULL;
return;
}
while (p != NULL) { // find a place for inserting new node
parent = p;
int keyLastDigit = key.at(key.length() - 1) - '0';
if (keyLastDigit % 2 == 0)
p = p->right;
else
p = p->left;
}
int keyLastDigit = key.at(key.length() - 1) - '0';
if (keyLastDigit % 2 == 0) {
TreeNode* node = new TreeNode; //new node allocation
//new node updation
node->item = key;
node->left = NULL;
node->right = NULL;
//adding new node to tree as right child of parent
parent->right = node;
} else if (keyLastDigit % 2 != 0) {
//new node allocation
TreeNode* node = new TreeNode;
//new node updation
node->item = key;
node->left = NULL;
node->right = NULL;
//adding new node to tree as left child of parent
parent->left = node;
}
}
/**
* main() function
*/
int main() {
string filePath = "./src/binaryTree.txt"; //change as per your path
ifstream infile(filePath.c_str()); //stream to read file
//check if file ok.
if (!infile) {
cerr << "Error reading or opening file!!!" << endl;
return EXIT_FAILURE;
}
string line; //to store line being read from file
//loop to read file
while (getline(infile, line)) {
//cout << line << endl;
stringstream ss(line);
int numTokens = 0;
string parent = "", leftChild = "", rightChild = "";
while (ss) {
string token;
ss >> token;
numTokens++;
if (numTokens == 1) {
parent = token;
if (search(root, parent) == NULL && parent.compare("") != 0)
insert_item(parent);
} else {
int l = token.length();
int last_digit;
if (l != 0) {
last_digit = token.at(l - 1) - '0';
if (last_digit % 2 == 0) {
rightChild = token;
if (rightChild.compare("") != 0) {
TreeNode *parentNode = search(root, parent);
//cout<<"parent key:"<<parentNode->item<<endl;
//cout<<"right:"<<rightChild<<endl;
TreeNode *newNode = new TreeNode;
newNode->item = rightChild;
newNode->left = NULL;
newNode->right = NULL;
parentNode->right = newNode;
//cout<<"inserted right:"<<parentNode->right->item<<endl;
}
} else {
leftChild = token;
if (leftChild.compare("") != 0) {
TreeNode *parentNode = search(root, parent);
//cout<<"parent key:"<<parentNode->item<<endl;
//cout<<"left:"<<leftChild<<endl;
TreeNode *newNode = new TreeNode;
newNode->item = leftChild;
newNode->left = NULL;
newNode->right = NULL;
parentNode->left = newNode;
//cout<<"inserted left:"<<parentNode->left->item<<endl;
}
}
}
}
}
ss.clear();
}
cout << "Preorder:";
preorder(root);
cout << endl;
cout << "Inorder:";
inorder(root);
cout << endl;
cout << "Postorder:";
postorder(root);
cout << endl;
int left_sub_tree_height = get_height(root->left);
int right_sub_tree_height = get_height(root->right);
cout << "The balance factor is:"
<< (left_sub_tree_height - right_sub_tree_height) << endl;
return EXIT_SUCCESS;
}
---------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.