Modify your solution to the first problem by first swapping all the right and le

ID: 3582340 • Letter: M

Question

Modify your solution to the first problem by first swapping all the right and left sub tree

(this is my problem)and then applying the binaryTreeSort function that you wrote in the first problem to the altered tree. Name this function binaryTreeSortDescending.

Write a program to test your function.

---------------binaryTree.h----------------------

I solved the first one but I didn't second problem I need helps~~

#ifndef H_binaryTree
#define H_binaryTree
#include
#include
using namespace std;
template
struct binaryTreeNode
{
elemType info;
binaryTreeNode *llink;
binaryTreeNode *rlink;
};

template
class binaryTreeType
{
public:
const binaryTreeType& operator=
(const binaryTreeType&);
//Overload the assignment operator.
bool isEmpty() const;
void inorderTraversal() const;
void preorderTraversal() const;
void postorderTraversal() const;
int treeHeight() const;
int treeNodeCount() const;
int treeLeavesCount() const;
   void swapSubtrees() const; //swapping function
void destroyTree();
binaryTreeType(const binaryTreeType& otherTree);
binaryTreeType();
~binaryTreeType();
protected:
binaryTreeNode *root;

private:
void copyTree(binaryTreeNode* &copiedTreeRoot,
binaryTreeNode* otherTreeRoot);
void destroy(binaryTreeNode* &p);
void inorder(binaryTreeNode *p) const;
void preorder(binaryTreeNode *p) const;
void postorder(binaryTreeNode *p) const;
int height(binaryTreeNode *p) const;
int max(int x, int y) const;
int nodeCount(binaryTreeNode *p) const;
int leavesCount(binaryTreeNode *p) const;

   void swapSubtreesOfNode(binaryTreeNode *p)const; //swapping
   //parent in the binary tree to which P points.
};
template
void binaryTreeType::swapSubtrees()const // swapping
{
   swapSubtreesOfNode(root);
}
template
void binaryTreeType::swapSubtreesOfNode(binaryTreeNode *p)const //swapping
{
   binaryTreeNode *temp;
   if (p != NULL)
   {
       temp = p->llink;
       p->llink = p->rlink;
       p->rlink = temp;
       swapSubtreesOfNode(p->llink);
       swapSubtreesOfNode(p->rlink);
   }
}
template
binaryTreeType::binaryTreeType()
{
root = NULL;
}

template
bool binaryTreeType::isEmpty() const
{
return (root == NULL);
}

template
void binaryTreeType::inorderTraversal() const
{
inorder(root);
}

template
void binaryTreeType::preorderTraversal() const
{
preorder(root);
}

template
void binaryTreeType::postorderTraversal() const
{
postorder(root);
}

template
int binaryTreeType::treeHeight() const
{
return height(root);
}

template
int binaryTreeType::treeNodeCount() const
{
return nodeCount(root);
}

template
int binaryTreeType::treeLeavesCount() const
{
return leavesCount(root);
}

template
void binaryTreeType::copyTree
(binaryTreeNode* &copiedTreeRoot,
binaryTreeNode* otherTreeRoot)
{
if (otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new binaryTreeNode;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
}
} //end copyTree

template
void binaryTreeType::inorder(binaryTreeNode *p) const
{
if (p != NULL)
{
inorder(p->llink);
cout << p->info << " ";
inorder(p->rlink);
}
}

template
void binaryTreeType::preorder(binaryTreeNode *p) const
{
   if (p != NULL)
   {
       cout<info<<" ";
       preorder(p->llink);
       preorder(p->rlink);
   }
}

template
void binaryTreeType::postorder(binaryTreeNode *p) const
{
if (p != NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout << p->info << " ";
}
}

//Overload the assignment operator
template
const binaryTreeType& binaryTreeType::
operator=(const binaryTreeType& otherTree)
{
if (this != &otherTree) //avoid self-copy
{
if (root != NULL) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);

if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else

return *this;
}

template
void binaryTreeType::destroy(binaryTreeNode* &p)
{
if (p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
}
}

template
void binaryTreeType::destroyTree()
{
destroy(root);
}

//copy constructor
template
binaryTreeType::binaryTreeType
(const binaryTreeType& otherTree)
{
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}

template
binaryTreeType::~binaryTreeType()
{
destroy(root);
}

template
int binaryTreeType::height(binaryTreeNode *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->llink), height(p->rlink));
}

template
int binaryTreeType::max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}

template
int binaryTreeType::nodeCount(binaryTreeNode *p) const
{
cout << "Write the definition of the function nodeCount"
<< endl;

return 0;
}

template
int binaryTreeType::leavesCount(binaryTreeNode *p) const
{
cout << "Write the definition of the function leavesCount"
<< endl;

return 0;
}

#endif

------------------binarySearchTree.h-------------------------

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include
#include
#include
#include
#include "binaryTree.h"
using namespace std;
template
class bSearchTreeType: public binaryTreeType
{
public:
bool search(const elemType& searchItem)const;
void insert(const elemType& insertItem);
void deleteNode(const elemType& deleteItem);
private:
void deleteFromTree(binaryTreeNode* &p);
};
template
bool bSearchTreeType::search(const elemType& searchItem) const
{
binaryTreeNode *current;
bool found = false;
if (root == NULL)
cerr << "Cannot search the empty tree." << endl;
else
{
current = root;
while (current != NULL && !found)
{
if (current->info == searchItem)
found = true;
else if (current->info > searchItem)
current = current->llink;
else
current = current->rlink;
}//end while
}//end else
return found;
}//end search
template
void bSearchTreeType::insert(const elemType& insertItem)
{
binaryTreeNode *current; //pointer to traverse the tree
binaryTreeNode *trailCurrent; //pointer behind current
binaryTreeNode *newNode; //pointer to create the node
newNode = new binaryTreeNode;
assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;
if (root == NULL)
root = newNode;
else
{
current = root;
trailCurrent = NULL;
while (current != NULL)
{
trailCurrent = current;
if (current->info == insertItem)
{
cerr << "The insert item is already in the list-";
cerr << "duplicates are not allowed." < return;
}
else
if (current->info > insertItem)
current = current->llink;
else
current = current->rlink;
}//end while
if (trailCurrent->info > insertItem)
trailCurrent->llink = newNode;
else
trailCurrent->rlink = newNode;
}
}//end insert

template
void bSearchTreeType::deleteNode(const elemType& deleteItem)
{
binaryTreeNode *current; //pointer to traverse the tree
binaryTreeNode *trailCurrent; //pointer behind current
bool found = false;

if (root == NULL)
cout << "Cannot delete from the empty tree." << endl;
else
{
current = root;
trailCurrent = root;

while (current != NULL && !found)
{
if (current->info == deleteItem)
found = true;
else
{
trailCurrent = current;

if (current->info > deleteItem)
current = current->llink;
else
current = current->rlink;
}
}//end while

if (current == NULL)
cout << "The delete item is not in the tree." << endl;
else if (found)
{
if (current == root)
deleteFromTree(root);
else if (trailCurrent->info > deleteItem)
deleteFromTree(trailCurrent->llink);
else
deleteFromTree(trailCurrent->rlink);
}//end if
}
}//end deleteNode

template
void bSearchTreeType::deleteFromTree
(binaryTreeNode* &p)
{
binaryTreeNode *current; //pointer to traverse the tree
binaryTreeNode *trailCurrent; //pointer behind current
binaryTreeNode *temp; //pointer to delete the node

if (p == NULL)
cerr << "Error: The node to be deleted is NULL." << endl;
else if(p->llink == NULL && p->rlink == NULL)
{
temp = p;
p = NULL;
delete temp;
}
else if(p->llink == NULL)
{
temp = p;
p = temp->rlink;
delete temp;
}
else if(p->rlink == NULL)
{
temp = p;
p = temp->llink;
delete temp;
}
else
{
current = p->llink;
trailCurrent = NULL;

while (current->rlink != NULL)
{
trailCurrent = current;
current = current->rlink;
}//end while

p->info = current->info;

if (trailCurrent == NULL) //current did not move;
//current == p->llink; adjust p
p->llink = current->llink;
else
trailCurrent->rlink = current->llink;

delete current;
}//end else
}//end deleteFromTree
#endif

----mian.cpp ----------------

#include
#include "binarySearchTree.h"
using namespace std;
int main()
{
   bSearchTreeType rootTree;
   int element;
   cout << " Enther the elements ending with -1" << endl;
   cin >> element;
   while (element != -1)
   {
       rootTree.insert(element);
       cin >> element;
   }
   cout << " Tree elements in inoreder: ";
   rootTree.inorderTraversal();
   cout << " The tree height is " << rootTree.treeHeight();
   rootTree.swapSubtrees();
   cout << " After swapping subtrees the tree elements in inorder:";
   rootTree.inorderTraversal();
   cout << " Tree height:" << rootTree.treeHeight() << endl;
   system("pause");
   return 0;
}

Explanation / Answer

Since , the first part of the question is not provided and the code is ambiguous, i'll simply explain how to swap the right and left subtree in a binary tree and then how to sort them.

here we have to swap the trees , we'll do that with the following steps :

-> for a tree node n and its left subtree l and right subtree r , swap l and r

-> now repeat this for the subtree's l and r

-> repeat for all nodes.

Code for this :

struct node {

int data;

struct node * right;

struct node * left;

}

void Swap( struct node * node)

{

if(node == NULL)
return;

else

{

struct node * temp;

//call the subtree nodes to swap recursively

swap (node->right);

swap(node->left);

//swap the current node's left and right subtrees

temp = node->left;

node->left = node->right;

node->right = temp;

}

Example of swapping with this function :

for the tree 4

2 5

since it is recursive it'll swap from the bottom up ... so the steps would be

2 5

followed by the final output

5 2

--------------------------------------------------------------

2) sorting the binary tree on the swapped tree

once we've swapped our binary tree , it's inorder traversal will give us the elements in the descending order.

inorder traversal is traversing the nodes of a tree - first the left subtree then root then right subtree

code -

void inorder(struct node * node)

{

if(node == NULL)

return ;

inorder(node->left);

*print the node value*

inorder(node->right);

}

example by taking our above swapped tree

5 2

its inorder traversal will be (left then root then right)

7 - 5 - 4 - 2

clearly this is in descending order , hence in the question it is asked to the change the sort functon to binaryTreeSortDescending.

Navigate

Modify your solution to question 4 above, replacing the IF statement with an EXI

Modify your word search array program (Homework program #1) to create a test cla

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

Modify your solution to the first problem by first swapping all the right and le

Question

Explanation / Answer

Related Questions

Navigate