/*
File: binaryTreeType.h
*/
#include <iostream>
using namespace std;
//Definition of the node
struct nodeType{
int info;
nodeType* llink;
nodeType* rlink;
};
//Definition of the class
class binaryTreeType{
public:
bool isEmpty();
// Function to determine whether the binary tree is empty.
// Postcondition : Return true if the binary tree is empty;
// otherwise, return false.
void inorderTraversal();
//Function to do a inorder traversal of the binary tree.
//Postcondition : The node of the binary tree output
// in the inorder sequence.
void preorderTraversal();
//Function to do a preorder traversal of the binary tree.
//Postcondition : the node of the binary tree output
// in the preorder sequence.
void postorderTraversal();
//Function to do a postorder traversal of the binary tree.
//Postcondition : The node of the binary tree output
// in the postorder sequence.
int treeHeight();
//Function to determine the height of the binary tree
//Postcondition : The height of the binary tree is returned.
int treeNodeCount();
//Function to determine the number of node in the binary tree
//Postcondition : THe number of node is the binary tree is returned
int treeLeaveCount();
//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& otherTree);
//copy constructor
binaryTreeType();
//defualt constructor
~binaryTreeType();
//destructor
protected :
nodeType *root;
private:
void copyTree(nodeType* &copiedTreeRoot,nodeType* otherTreeRoot);
//Function to make a copy of the binary tree to
//whic othertreeRoot points.
//Postcondition : The pointer copiedTreeRoot points to the
// root of the copied binary tree.
void destroy(nodeType* &p);
//Function to destroy the binary tree to which p points.
//Postcondition : The node of the binary tre to which
// p points are dellocated ; p = NULL.
void inorder(nodeType *p);
//Function to do inorder traversal of the binary tree to which
// p points.
//Postcondition : The node of the binary tree to which p points
// are output in the inorder sequence.
void preorder(nodeType *p);
//Funtion to do a preorder traversal of the binary tree to which
// a points.
//Postcondition : The node of the binary tree to which p
// points are output in the preorder sequence.
void postorder(nodeType *p);
//Function to do postorder traversal of the binary free to which p points.
//Postcodition : The node of the bianry tree to which p
// points are output in the postorder sequence.
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 *p);
//Function to determine the number of node in the binary tree
// to which p points.
//Postcondition : The number of node in the binary tree
// to which p points.
int leavesCount(nodeType *p);
//Function to determine the number of leaves in the binary
// tree to which p points.
//Postcondition : The number of leaves in the binary tree
// to which p points is returned.
int height(nodeType *p);
};
bool binaryTreeType::isEmpty(){
return root == NULL;
}
binaryTreeType::binaryTreeType(){
root = NULL;
}
void binaryTreeType::inorderTraversal(){
inorder(root);
}
void binaryTreeType::preorderTraversal(){
preorder(root);
}
void binaryTreeType::postorderTraversal(){
postorder(root);
}
int binaryTreeType::treeHeight(){
return height(root);
}
int binaryTreeType::treeNodeCount(){
return nodeCount(root);
}
int binaryTreeType::treeLeaveCount(){
return leavesCount(root);
}
void binaryTreeType::inorder(nodeType* p){
if(p != NULL){
inorder(p->llink); // L node
cout<< p->info << " "; // Visit node
inorder(p->rlink); // R node
}
}
void binaryTreeType::postorder(nodeType* p){
if(p != NULL){
postorder(p->llink); //L node
postorder(p->rlink); //R node
cout<< p->info <<" "; //Visit node
}
}
void binaryTreeType::preorder(nodeType* p){
if(p != NULL){
cout<< p->info<<" ";
preorder(p->llink);
preorder(p->rlink);
}
}
int binaryTreeType::height(nodeType* p){
if(p == NULL)
return 0;
else
return 1+max(height(p->llink),height(p->rlink));
}
int binaryTreeType::max(int x, int y){
if(x>=y)
return x;
else
return y;
}
void binaryTreeType::copyTree(nodeType*& copiedTreeRoot,nodeType* otherTreeRoot){
if(otherTreeRoot == NULL){
copiedTreeRoot = NULL;
}else{
copiedTreeRoot = new nodeType;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->llink,otherTreeRoot->llink);
copyTree(copiedTreeRoot->rlink,otherTreeRoot->rlink);
}
}
void binaryTreeType::destroy(nodeType* &p){
if(p != NULL){
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
}
}
void binaryTreeType::destroyTree(){
destroy(root);
}
binaryTreeType::binaryTreeType(const binaryTreeType &otherTree){
if(otherTree.root == NULL)
root = NULL;
else
copyTree(root,otherTree.root);
}
binaryTreeType::~binaryTreeType(){
destroy(root);
}
int binaryTreeType::nodeCount(nodeType* p){
if(p == NULL)
return 0;
return (nodeCount(p->llink) + nodeCount(p->rlink)+1);
}
int binaryTreeType::leavesCount(nodeType* p){
if(p == NULL)
return 0;
if((p->llink ==NULL ) && (p->rlink == NULL))
return 1;
return (leavesCount(p->llink)+leavesCount(p->rlink));
}
|
