Binary tree
I have this problem to submit it tomorrow
I have to do it
pleeze help me
Add the implementation of the following functions to the class binaryTreeType:
1. nodeCount that takes as a parameter a pointer to the root node of a binary tree and returns the number of nodes in a binary tree.
2. leavesCount that takes as a parameter a pointer to the root node of a binary tree and returns the number of leaves in a binary tree.
3. swapSubTrees, that swaps all of the left and right sub trees of a binary tree.
4. singleParent that returns the number of nodes in a binary tree that have only one child.
Now write a main to test your functions, but first create a binary Search tree, to test the functions on.
Hint: notice that in the binaryTreeType class there are 2 versions for each function one that does not take parameters and the other one takes a pointer to the root as parameter, in the main you should call the one without parameters while in the recursive calls inside the class you have to call the one that takes parameter, in the same way you use the inorder and postorder functions

I will put my answer

## Recommended Answers

int maxSize=14;
int inputArray[maxSize]=(60,50,70,30,53,80,35,57,75,32,40,77,48,45);

Another thing i do not konw how to initilize this array

1. Use braces `{...}` instead of parentheses for initializator-list.
2. Avoid using red color (and other rainbow) effects. For example I (and may others) hate long red lines ;)
3. Use code …

Not true..

1. Use braces `{...}` instead of parentheses for initializator-list.

that is true..

## All 8 Replies

``````#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>
#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>

using namespace std;

template<class elemType>
struct nodeType
{
elemType	           info;
nodeType<elemType>  *llink;
nodeType<elemType>  *rlink;
};

//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty();
//Function to determine if the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
//               otherwise, returns false.
void inorderTraversal();
//Function to do an inorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
//               in the inorder sequence.
void preorderTraversal();
//Function to do a preorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
//               in the preorder sequence.
void postorderTraversal();
//Function to do a postorder traversal of the binary tree.
//Postcondition: The nodes of the binary tree are output
//               in the postorder sequence.

int treeHeight();
//Function to deteremine the height of the binary tree.
//Postcondition: The height of the binary tree is returned.
int treeNodeCount();
//Function to determine the number of nodes in the
//binary tree.
//Postcondition: The number of nodes in the binary tree
//               is returned.
int treeLeavesCount();
//Function to determine the number of leaves in the
//binary tree.
//Postcondition: The number of leaves in the binary tree
//               is returned.
void destroyTree();
//Deallocates the memory space occupied by the binary tree.
//Postcondition: root = NULL;

binaryTreeType(const binaryTreeType<elemType>& otherTree);
//copy constructor

binaryTreeType();
//default constructor

~binaryTreeType();
//destructor

protected:
nodeType<elemType> *root;
int	leafCnt;

private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
//Function to make a copy of the binary tree to
//which otherTreeRoot points.
//Postcondition: The pointer copiedTreeRoot points to
//               the root of the copied binary tree.

void destroy(nodeType<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: The nodes of the binary tree to which
//               p points are deallocated.
//               p = NULL.

void inorder(nodeType<elemType> *p);
//Function to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
//               points are output in the inorder sequence.
void preorder(nodeType<elemType> *p);
//Function to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
//               points are output in the preorder sequence.
void postorder(nodeType<elemType> *p);
//Function to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: The nodes of the binary tree to which p
//               points are output in the postorder sequence.

int height(nodeType<elemType> *p);
//Function to determine the height of the binary tree
//to which p points.
//Postcondition: The height of the binary tree to which p
//               points is returned.

int max(int x, int y);
//Function to determine the larger of x and y.
//Postcondition: The larger of x and y is returned.

int nodeCount(nodeType<elemType> *p);
//Function to determine the number of nodes in the binary
//tree to which p points.
//Postcondition: The number of nodes in the binary tree
//               to which p points is returned.

int leavesCount(nodeType<elemType> *p);
//Function to determine the number of leaves in the binary
//tree to which p points.
//Postcondition: The number of nodes in the binary tree
//               to which p points is returned.
int childCount(nodeType<elemType> *p);
};

//Definition of member functions

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
nodecnt=0;
leafCnt=0;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
return leavesCount(root);
}

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

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
if(p != NULL)
{
inorder(p->llink);
cout<<p->info<<" ";
inorder(p->rlink);

}
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
if(p != NULL)
{
cout<<p->info<<" ";
preorder(p->llink);
preorder(p->rlink);

}
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
if(p != NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout<<p->info<<" ";

}
}

//Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& 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 <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
if(p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;

}
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}

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

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}

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

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

template<class elemType>
int	binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p){
// Count the nodes in the binary tree to which
// root points, and return the answer.
if ( p == NULL )
return 0;  // The tree is empty.  It contains no nodes.
else {
int count = 1;   // Start by counting the root.
count += nodeCount(root->left);  // Add the number of nodes
//     in the left subtree.
count += nodeCount(root->right); // Add the number of nodes
//    in the right subtree.
return count;  // Return the total.
}
}

template<class elemType>
int	binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p){
cout<<"The top element is:"<<p->info<<endl;
if(p->llink!=NULL)
leafCnt+=leavesCount(p->llink);
if(p->rlink!=NULL)
leafCnt+=leavesCount(p->rlink);
return leafCnt;
}
template<class elemType>
int binaryTreeType<elemType>::childCount(nodeType<elemType> *p){
if (p == NULL)
return 0;
}

//bbbbbbbbsearchtreee

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
bool search(const elemType& searchItem);
//Function to determine if searchItem is in the binary
//search tree.
//Postcondition: Returns true if searchItem is found in the
//             binary search tree; otherwise, returns false.

void insert(const elemType& insertItem);
//Function to insert insertItem in the binary search tree.
//Postcondition: If no node in the binary search tree has
//           the same info as insertItem, a node with the
//           info insertItem is created and inserted in the
//binary search tree.

void deleteNode(const elemType& deleteItem);
//Function to delete deleteItem from the binary search tree
//Postcondition: If a node with the same info as deleteItem
//               is found, it is deleted from the binary
//               search tree.

private:
void deleteFromTree(nodeType<elemType>* &p);
//Function to delete the node, to which p points, from the
//binary search tree.
//Postcondition: The node to which p points is deleted
//               from the binary search tree.
};

template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType> *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<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType> *current;  //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
nodeType<elemType> *newNode;  //pointer to create the node

newNode = new nodeType<elemType>;
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."<<endl;
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<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
nodeType<elemType> *current;  //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
bool found = false;

if(root == NULL)
cerr<<"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<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(nodeType<elemType>* &p)
{
nodeType<elemType> *current;    //pointer to traverse
//the tree
nodeType<elemType> *trailCurrent;   //pointer behind current
nodeType<elemType> *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

int main(){
int maxSize=14;
int inputArray[maxSize]=(60,50,70,30,53,80,35,57,75,32,40,77,48,45);
char inChoice;
bSearchTreeType<int> myTree;
for (int i=0;i<maxSize;i++)
myTree.insert(inputArray[i]);
cout<<"Display output using:\n a)inorder traversal\nb)preorder traversal";
cout<<"\nc)postorder traversal\n \n Enter choice:";
cin>>inChoice;

cout<<"\n\n";
switch(inChoice)
{
case'a':case'A':
myTree.inorderTraversal();
break;

case'b':case'B':
myTree.preorderTraversal();
break;
case'c':case'C':
myTree.postorderTraversal();
break;
}
cout<<endl;
cout<<"\n The number of nodes in the tree is-are:"<<myTree.treeNodeCount()<<endl;
cout<<"\n The number of leaves in the tree is-are:"<<myTree.treeLeavesCount()<<endl;
cout<<endl;
return 0;
}``````

l hope that any body help me
I will be crazy
I can not think more than this
help pleaze

int maxSize=14;
int inputArray[maxSize]=(60,50,70,30,53,80,35,57,75,32,40,77,48,45);

Another thing i do not konw how to initilize this array

int maxSize=14;
int inputArray[maxSize]=(60,50,70,30,53,80,35,57,75,32,40,77,48,45);

Another thing i do not konw how to initilize this array

1. Use braces `{...}` instead of parentheses for initializator-list.
2. Avoid using red color (and other rainbow) effects. For example I (and may others) hate long red lines ;)
3. Use code tags for your (properly indented) sources (see forum rules):
[code=c++] source(s)

[/code]
It's impossible (at least annoying) to read these sources w/o some kind of formatting...

template<class elemType>int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p){ // Count the nodes in the binary tree to which // root points, and return the answer. if ( p == NULL ) return 0; // The tree is empty. It contains no nodes. else { int count = 1; // Start by counting the root. count += nodeCount(root->left); // Add the number of nodes // in the left subtree. count += nodeCount(root->right); // Add the number of nodes // in the right subtree. return count; // Return the total. }} template<class elemType>int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p){ cout<<"The top element is:"<<p->info<<endl; if(p->llink!=NULL) leafCnt+=leavesCount(p->llink); if(p->rlink!=NULL) leafCnt+=leavesCount(p->rlink); return leafCnt;}template<class elemType>int binaryTreeType<elemType>::childCount(nodeType<elemType> *p){ if (p == NULL) return 0;}

int main(){ int maxSize=14; int inputArray[maxSize]=(60,50,70,30,53,80,35,57,75,32,40,77,48,45); char inChoice; bSearchTreeType<int> myTree; for (int i=0;i<maxSize;i++)myTree.insert(inputArray); cout<<"Display output using:\n a)inorder traversal\nb)preorder traversal"; cout<<"\nc)postorder traversal\n \n Enter choice:"; cin>>inChoice; cout<<"\n\n"; switch(inChoice) { case'a':case'A': myTree.inorderTraversal(); break; case'b':case'B': myTree.preorderTraversal(); break; case'c':case'C': myTree.postorderTraversal(); break; } cout<<endl; cout<<"\n The number of nodes in the tree is-are:"<<myTree.treeNodeCount()<<endl; cout<<"\n The number of leaves in the tree is-are:"<<myTree.treeLeavesCount()<<endl; cout<<endl; return 0;}

I want any body just to tell me this one is true or not!!!

``````template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p){
// Count the nodes in the binary tree to which
// root points, and return the answer.
if ( p == NULL )
return 0;  // The tree is empty.  It contains no nodes.
else {
int count = 1;   // Start by counting the root.
count += nodeCount(root->left);  // Add the number of nodes
//     in the left subtree.
count += nodeCount(root->right); // Add the number of nodes
//    in the right subtree.
return count;  // Return the total.
}
}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p){
cout<<"The top element is:"<<p->info<<endl;
if(p->llink!=NULL)
leafCnt+=leavesCount(p->llink);
if(p->rlink!=NULL)
leafCnt+=leavesCount(p->rlink);
return leafCnt;
}
template<class elemType>
int binaryTreeType<elemType>::childCount(nodeType<elemType> *p){
if (p == NULL)
return 0;
}
``````

pleeze help me in those functions >>><<< are they true or false

commented: Why do you ignore whats said? [B]Use code tags[/B] -1

Not true..

1. Use braces `{...}` instead of parentheses for initializator-list.

that is true..

nodeCount, leavesCount and singleParent can all be written using a similar footprint. First declare variables in the tree to act as counters for the number of nodes, the number of leaves and the number of singletons and initialize them to zero in the default constructor. Declare the functions with private access, with return type void, and accepting a node pointer. Call them from a public method if tree isn't empty. The public method returns the respective member variable. The private methods each traverse the tree (you can use whatever traversal strategy you want) with recursive function calls and a single "processing statement" just like the traversal methods you've already written. The "processing statement" isn't the cout statement used in the traversing methods you've already written, however. Instead it is statement that does what the function's name implies by incrementing the respective member variable. In the node count method the "processing statement" simply increments the node count variable of the tree. In leavesCount() it checks if the node is a leaf and if so it increments the leaf count variable. In the singleParent() method the "processing statement" determines whether the node has a single "child" (which may be either a llink or rlink that is NULL, but only one of the links can be NULL, not both) and increments the respective counter.

I haven't worked out the swapSubTrees yet though I suspect it would work much like a routine swap, that is, for each node in the tree found during a traversal assign llink to a temp node pointer, assign rlink to llink, and assign temp to rlink.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.