***** C++ ******* Use the tree class Add a method to your tree class that will r
ID: 656346 • Letter: #
Question
***** C++ *******
Use the tree class
Add a method to your tree class that will return the number of nodes in a tree. Name - treeNodecount
Add two methods one that will return the number of node on the right side of the tree, the other the method will return the number of nodes on the left side of the tree. Names - treeLeftnodeCount, treeRightnodeCount.
This is the code that I have so far, feel free to edit it as much as you want:
// BinaryTree.cpp : Defines the entry point for the console application.
// Michael Lightbody
#include "stdafx.h"
#include <iostream>
using namespace std;
template <class datatype>
class treenode{
public:
datatype data;
treenode<datatype> *lchild, *rchild;
};
template<class datatype>
class btree{
private:
treenode<datatype> *root;
public:
btree();
bool tree_empty(void);
void insertdata(datatype x);
void inserttree(treenode<datatype> *&p, datatype d);
void inorder(treenode<datatype> *p);
void printinorder(void);
void preorder(treenode<datatype> *p);
void printpreorder(void);
void postorder(treenode<datatype> *p);
void printpostorder(void);
void deletevalue(datatype v);
void deltree(datatype val, treenode<datatype> *&p);
treenode<datatype>* findmin(treenode<datatype> *p);
};
template<class datatype>
treenode<datatype>* btree<datatype>::findmin(treenode<datatype> *p){
if(p->lchild == NULL)
return (p);
else
return(findmin(p->lchild));
};
template<class datatype>
void btree<datatype>::deltree(datatype val, treenode<datatype> *&p){ //Does NOT delete the node
treenode<datatype> *buff;
if(p != NULL)
if(val < p->data)
deltree(val,p->lchild);
else
if(val > p->data)
deltree(val, p->rchild);
else
if(p->lchild == NULL && p->rchild == NULL)
p= NULL;
else
if(p->lchild == NULL)
p= p->rchild;
else
if(p->rchild == NULL)
p = p->lchild;
else
{
buff = findmin(p->rchild);
buff->lchild = p->lchild;
p = p->rchild;
}
};
template<class datatype>
void btree<datatype>::deletevalue(datatype v){
deltree(v,root);
};
template<class datatype>
void btree<datatype>::postorder(treenode<datatype> *p){
if(p!= NULL){
postorder(p->lchild);
postorder(p->rchild);
cout<< p->data << " ";
}
};
template<class datatype>
void btree<datatype>::printpostorder(void){
postorder(root);
};
template<class datatype>
void btree<datatype>::preorder(treenode<datatype> *p){
if(p!= NULL){
cout<< p->data << " ";
preorder(p->lchild);
preorder(p->rchild);
}
};
template<class datatype>
void btree<datatype>::printpreorder(void){
preorder(root);
};
template<class datatype>
void btree<datatype>::inorder(treenode<datatype> *p){
if(p!= NULL){
inorder(p->lchild);
cout<< p->data << " ";
inorder(p->rchild);
}
};
template<class datatype>
void btree<datatype>::printinorder(void){
inorder(root);
};
template<class datatype>
void btree<datatype>::inserttree(treenode<datatype> *&p, datatype d){
if(p == NULL){
p = new treenode<datatype>;
p->data = d;
p->lchild = NULL;
p->rchild = NULL;
}else{
if(p->data > d)
inserttree(p->lchild,d);
else
inserttree(p->rchild,d);
}
};
template<class datatype>
void btree<datatype>::insertdata(datatype x){
inserttree(root,x);
};
template<class datatype>
btree<datatype>::btree(){
root =NULL;
};
template<class datatype>
bool btree<datatype>::tree_empty(){
bool x = true;
if(root == NULL){
x = true;
}else{
x = false;
}
return x;
};
int _tmain(int argc, _TCHAR* argv[])
{
btree<int> testTree;
testTree.insertdata(50); //28 is the root.
testTree.insertdata(30); // The values that will be based off the root.
testTree.insertdata(20);
testTree.insertdata(10);
testTree.insertdata(45);
testTree.insertdata(35);
testTree.insertdata(46);
testTree.insertdata(70);
testTree.insertdata(60);
testTree.insertdata(80);
/*
testTree.insertdata(68);
testTree.insertdata(50);
testTree.insertdata(40);
testTree.insertdata(55);
testTree.insertdata(28);
testTree.insertdata(10);
testTree.insertdata(35);
testTree.insertdata(30);
testTree.insertdata(62);
testTree.insertdata(60);
testTree.insertdata(95); //28 is the root.
testTree.insertdata(75); // The values that will be based off the root.
testTree.insertdata(72);
testTree.insertdata(80);
testTree.insertdata(85);
testTree.insertdata(90);
testTree.insertdata(88);
testTree.insertdata(99);
testTree.insertdata(96);
testTree.insertdata(98);
testTree.insertdata(58);
if(testTree.tree_empty()){ //Checks to see if testTree is empty, which it is not.
cout<<"Tree empty"<<endl;
}else{
cout<<"Tree is not empty"<<endl;
}
/*
testTree.deletevalue(50);
testTree.deletevalue(90);
testTree.deletevalue(75);
*/
testTree.deletevalue(30);
testTree.deletevalue(50);
cout<<""<<endl;
cout<<"Print Pre-Order:"<<endl;
testTree.printpreorder();
cout<<""<<endl;
cout<<"Print in order:"<<endl;
testTree.printinorder();
cout<<""<<endl;
cout<<"Print Post-Order:"<<endl;
testTree.printpostorder();
return 0;
}
/*
Print Pre-Order:
70 60 45 35 20 10 46 80
Print in order:
10 20 35 45 46 60 70 80
Print Post-Order:
10 20 35 46 45 60 80 70
*/
Explanation / Answer
template<class datatype>
int btree<datatype>:: treeNodecount(treenode<datatype> *p)
{
int count = 1;
if (p == NULL)
return 0;
else
{
count += treeNodeCount(p->lchild);
count += treeNodeCount (p->rchild);
return count;
}
}
template<class datatype>
int btree<datatype>:: treeLeftnodeCount (treenode<datatype> *p)
{
int count = 0;
if (p == NULL)
return 0;
else
{
count += treeLeftnodeCount (p->lchild);
count = treeLeftnodeCount (p->rchild);
return count;
}
}
template<class datatype>
int btree<datatype>:: treeRightnodeCount (treenode<datatype> *p)
{
int count = 0;
if (p == NULL)
return 0;
else
{
count = treeRightnodeCount (p->lchild);
count += treeRightnodeCount (p->rchild);
return count;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.