Question

c++

creat a bst.h

with constructor, copyconstructor, overloaded assignment operator, destructor, count leaves, count full nodes, print ancestors

using c++

create a binary search tree class with tree.h class tree.cpp class and a driver to test the method.

tree.h need to define the copy constructor, overloaded assignment operator, destructor, find height, print ancesstor, print post order traversal, print iterative in order traversal, constructor, find key, count full nodes, count leaves,

Answer 1

-------------------------------------tree.h----------------------------------------

class tree
{ 
    int data; 
    tree *left, *right; 
    public: 
    tree(); 
    tree(int v);
    tree(tree *t); 
    tree* insert(tree *, int); 
    void inorder(tree *);
    tree& operator =(tree &t);
    int height(tree *);
    void postorder(tree *);
    tree* search(tree *,int key);
    int countleaves(tree *);
    int fullnodes(tree *);
    bool ancestors(tree *,int key);
    ~tree();
}; 

------------------------------------------tree.cpp-----------------------------------------------------

#include <iostream>
#include "tree.h"
#include<stack>
using namespace std;

// constructor
tree::tree(){
    data=0;
    left=right=NULL;
}
// parametrized constructor
tree::tree(int v){
    data=v;
    left=right=NULL;
}
// copy constructor
tree::tree(tree *t){
    this->data=t->data;
    this->left=t->left;
    this->right=t->right;
}
// overload assignment operator
tree& tree::operator=(tree &t){
    tree te(t);
    return te;
}
// function to insert nodes in tree
tree* tree::insert(tree *root,int key){
    if(!root){
        return new tree(key);
    }
    if(key>root->data)// if key is > than root's value
        root->right=insert(root->right,key);
    else
        root->left=insert(root->left,key);
    return root;
}
// function to print nodes of tree in postorder
void tree::postorder(tree *root){
    if(root){
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<" ";
    }
}
// function to print nodes of tree in inorder iteratively
void tree::inorder(tree *root){
    stack<tree *> s; 
    tree *temp=root; 
    while(temp!=NULL||s.empty()==false) 
    { 
        // move to left most node of temp
        while(temp!=NULL) 
        {
            s.push(temp); 
            temp=temp->left; 
        } 
        temp=s.top(); 
        s.pop(); 
        cout<<temp->data<< " "; 
        temp=temp->right; 
    } 
}
// function to find height of tree
int tree::height(tree *root){
    if(root){
        int l=height(root->left);
        int r=height(root->right);
        if(l>r)
            return l+1;
        else
            return r+1;
    }
    return 0;
}
// function to search for a key in tree
tree* tree::search(tree *root,int key){
    if(root==NULL||root->data==key)
        return root;
    if(root->data>key)// if root's data is > given key then seatch in left subtree
        return search(root->left,key);
    return search(root->right,key);// else search right subtree
}
// function to count full nodes in tree
int tree::fullnodes(tree *root){
    if(root==NULL)
        return 0;
    int c=0;
    if(root->left&&root->right)
        c++;
    c+=fullnodes(root->left)+fullnodes(root->right);
    return c;
}
// function to count leaves in tree
int tree::countleaves(tree *root){
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)// if there is only 1 node in tree
        return 1;
    else
        return countleaves(root->left)+countleaves(root->right);
}
// function to print ancestors of key in tree
bool tree::ancestors(tree *root,int key){
    if(root==NULL) 
        return false; 
    if(root->data==key) 
        return true; 
    // check in left or right subtree  
    if (ancestors(root->left,key) || ancestors(root->right,key) ) 
    { 
        cout<<root->data<<" "; 
        return true; 
    } 
    return false;
}
// destructor
tree::~tree(){
    delete left;
    delete right;
}

--------------------------------------------------------main.cpp----------------------------------------------

#include "tree.h"
#include<iostream>
using namespace std;
int main()
{
    tree t,*root=NULL;
    root=t.insert(root,50);
    t.insert(root,30);
    t.insert(root,20);
    t.insert(root,40);
    t.insert(root,70);
    cout<<"Postorder traversal is: ";
    t.postorder(root);
    cout<<"\nIndorder traversal is: ";
    t.inorder(root);
    cout<<"\nHeight of tree is: "<<t.height(root);
    cout<<"\nCount of leaf nodes: "<<t.countleaves(root);
    cout<<"\nCount of full nodes: "<<t.fullnodes(root);
    cout<<"\nAncestors for key 40 are: ";
    t.ancestors(root,40);
    cout<<"\nSearch for value 60 in tree: ";
    if(t.search(root,60)==0)
        cout<<"Not found in tree!"<<endl;
    else
        cout<<"Found in tree"<<endl;
    // deleting the entire tree
    delete root;
    return 0;
}

////////////////////////tree.h

//////////////////////tree.cpp

/////////////////////main.cpp