C++ Problem Add two functions to a binary tree class. The first function returns
ID: 3582245 • Letter: C
Question
C++ Problem
Add two functions to a binary tree class. The first function returns an array list or vector. It is modified version of the public inorderTraversal() function. The first function invokes the second function, a modified version of the private inorder() function. The second function copies the tree nodes' data to the array list or vector as it visits each node. .
Write a program to test your function.
Will give good points for right code
The Binary Tree is defined as followed.
#ifndef H_binaryTree
#define H_binaryTree
#include
using namespace std;
template
struct binaryTreeNode
{
elemType info;
binaryTreeNode *llink;
binaryTreeNode *rlink;
};
template
class binaryTreeType
{
public:
const binaryTreeType& operator=
(const binaryTreeType&);
bool isEmpty() const;
void inorderTraversal() const;
void preorderTraversal() const;
void postorderTraversal() const;
int treeHeight() const;
int treeNodeCount() const;
int treeLeavesCount() const;
void destroyTree();
int singleParent();
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;
int singleP(binaryTreeNode *p);
};
template
int binaryTreeType::singleParent()
{
return singleP(root);
}
template
int binaryTreeType::singleP(binaryTreeNode *p)
{
if (p == NULL)
return 0;
else if (p->llink == NULL && p->rlink != NULL)
return 1 + singleP(p->rlink);
else if (p->llink != NULL && p->rlink == NULL)
return 1 + singleP(p->llink);
else
{
return singleP(p->llink) + singleP(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);
}
}
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 << p->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 << " ";
}
}
template
const binaryTreeType& binaryTreeType::
operator=(const binaryTreeType& otherTree)
{
if (this != &otherTree)
{
if (root != NULL)
destroy(root);
if (otherTree.root == NULL)
root = NULL;
else
copyTree(root, otherTree.root);
}
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);
}
template
binaryTreeType::binaryTreeType
(const binaryTreeType& otherTree)
{
if (otherTree.root == NULL)
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
{
if (p == NULL)
return 0;
else
{
return 1 + nodeCount(p->llink) + nodeCount(p->rlink);
}
}
template
int binaryTreeType::leavesCount(binaryTreeNode *p) const
{
if (p == NULL)
return 0;
else
if (p->llink == NULL && p->rlink == NULL)
return 1;
else
return leavesCount(p->llink) + leavesCount(p->rlink);
}
#endif
#ifndef H_binarySearchTree
#define H_binarySearchTree
#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;
}
}
return found;
}
template
void bSearchTreeType::insert(const elemType& insertItem)
{
binaryTreeNode *current;
binaryTreeNode *trailCurrent= NULL;
binaryTreeNode *newNode;
newNode = new binaryTreeNode;
assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;
if (root == NULL)
root = newNode;
else
{
current = root;
while (current != NULL)
{
trailCurrent = current;
if (current->info == insertItem)
{
cerr << "The insert item is already in the list-";
cerr << "duplicates are not allowed."
<< insertItem << endl;
return;
}
else if (current->info > insertItem)
current = current->llink;
else
current = current->rlink;
}
if (trailCurrent->info > insertItem)
trailCurrent->llink = newNode;
else
trailCurrent->rlink = newNode;
}
}
template
void bSearchTreeType::deleteNode(const elemType& deleteItem)
{
binaryTreeNode *current;
binaryTreeNode *trailCurrent;
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;
}
}
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);
}
}
}
template
void bSearchTreeType::deleteFromTree
(binaryTreeNode* &p)
{
binaryTreeNode *current;
binaryTreeNode *trailCurrent;
binaryTreeNode *temp;
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;
}
p->info = current->info;
if (trailCurrent == NULL)
p->llink = current->llink;
else
trailCurrent->rlink = current->llink;
delete current;
}
}
#endif
Explanation / Answer
/*Program of insertion and deletion in B tree*/
#include<stdlib.h>
#include<stdio.h>
#define M 5
struct node{
int n; /* n < M No. of keys in node will always less than order of B tree */
int keys[M-1]; /*array of keys*/
struct node *p[M]; /* (n+1 pointers will be in use) */
}*root=NULL;
enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
void insert(int key);
void display(struct node *root,int);
void DelNode(int x);
void search(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);
int main()
{
int key;
int choice;
printf("Creation of B tree for node %d ",M);
while(1)
{
printf("1.Insert ");
printf("2.Delete ");
printf("3.Search ");
printf("4.Display ");
printf("5.Quit ");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the key : ");
scanf("%d",&key);
insert(key);
break;
case 2:
printf("Enter the key : ");
scanf("%d",&key);
DelNode(key);
break;
case 3:
printf("Enter the key : ");
scanf("%d",&key);
search(key);
break;
case 4:
printf("Btree is : ");
display(root,0);
break;
case 5:
exit(1);
default:
printf("Wrong choice ");
break;
}/*End of switch*/
}/*End of while*/
return 0;
}/*End of main()*/
void insert(int key)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf("Key already available ");
if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/
enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M - 1)
{
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is last*/
if (pos == M - 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are maximum and position of node to be inserted is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M - 1)/2;
(*upKey) = ptr->keys[splitPos];
(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/
void display(struct node *ptr, int blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf(" ");
for (i=0; i < ptr->n; i++)
printf("%d ",ptr->keys[i]);
printf(" ");
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/
void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf("Search path: ");
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(" %d",ptr->keys[i]);
printf(" ");
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
{
printf("Key %d found in position %d of last dispalyed node ",key,i);
return;
}
ptr = ptr->p[pos];
}
printf("Key %d is not available ",key);
}/*End of search()*/
int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/
void DelNode(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf("Key %d is not available ",key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}/*End of switch*/
}/*End of delnode()*/
enum KeyStatus del(struct node *ptr, int key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
struct node **p,*lptr,*rptr;
if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M - 1)/2;/*Minimum number of keys*/
pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key < key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}/*End of if */
if (pos < n && key == key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}/*End of while*/
key_arr[pos] = qp->keys[nkey-1];
qp->keys[nkey - 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;
if (pos > 0 && p[pos-1]->n > min)
{
pivot = pos - 1; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i--)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = key_arr[pivot];
rptr->p[0] = lptr->p[lptr->n];
key_arr[pivot] = lptr->keys[--lptr->n];
return Success;
}/*End of if */
if (pos<n && p[pos+1]->n > min)
{
pivot = pos; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
key_arr[pivot] = rptr->keys[0];
lptr->n++;
rptr->n--;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}/*End of for*/
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}/*End of if */
if(pos == n)
pivot = pos-1;
else
pivot = pos;
lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}/*End of del()*/
//Hope this will be helful to you. I am giving a new type of example of binary tree.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.