Question

C++ tree program (please do NOT use struct Node, use classes)

Program 1 Implement a Binary tree using an array

Program 2 Implement a tree using linked list - pointer Binary Tree

Program 3 - Convert program 1 to a template

(include screenshots please of output)

Answer 1

Eg: the location of node 3 in the array is 3. So it’s left child will be placed at 2*3 = 6.

Its right child will be at the location 2*3 +1 = 7. As we can see in the array, children of 3 which are 6 and 7 are placed at location 6 and 7 in the array.

Used structure to declare a single node and then using a class, we develop a linked list of nodes.

#include<iostream>

using namespace std;

struct bintree_node{

    bintree_node *left;

    bintree_node *right;

    int data;

} ;

class bst{

    bintree_node *root;

    public:

    bst(){

        root=NULL;

    }

    int isempty() {

        return(root==NULL);

    }

    void insert(int item);

    void displayBinTree();

    void printBinTree(bintree_node *);

     

};

void bst::insert(int item){

    bintree_node *p=new bintree_node;

    bintree_node *parent;

    p->data=item;

    p->left=NULL;

    p->right=NULL;

    parent=NULL;

    if(isempty())

        root=p;

    else{

        bintree_node *ptr;

        ptr=root;

        while(ptr!=NULL){

            parent=ptr;

            if(item>ptr->data)       

                ptr=ptr->right;

            else

                ptr=ptr->left;

        }  

        if(item<parent->data)

            parent->left=p;

        else

            parent->right=p;

    }

}

void bst::displayBinTree(){

    printBinTree(root);

}

void bst::printBinTree(bintree_node *ptr){

    if(ptr!=NULL){

        printBinTree(ptr->left);

        cout<<" "<<ptr->data<<"     ";

        printBinTree(ptr->right);

    }

}

int main(){

    bst b;

    b.insert(20);

    b.insert(10);

    b.insert(5);

    b.insert(15);

    b.insert(40);

    b.insert(45);

    b.insert(30);

    cout<<"Binary tree created: "<<endl;

    b.displayBinTree();

}

Output:

Binary tree created:

5       10       15       20       30       40       45

PROGRAM 2:

struct TreeNode {
              int item;         // The data in this node.
              TreeNode *left;   // Pointer to the left subtree.
              TreeNode *right;  // Pointer to the right subtree.
           }

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

 void preorderPrint( TreeNode *root ) {
           // Print all the items in the tree to which root points.
           // The item in the root is printed first, followed by the
           // items in the left subtree and then the items in the
           // right subtree.
        if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
           cout << root->item << " ";      // Print the root item.
           preorderPrint( root->left );    // Print items in left subtree.
           preorderPrint( root->right );   // Print items in right subtree.
        }
     } // end preorderPrint()

void postorderPrint( TreeNode *root ) {
           // Print all the items in the tree to which root points.
           // The items in the left subtree are printed first, followed 
           // by the items in the right subtree and then the item in the
           // root node.
        if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
           postorderPrint( root->left );    // Print items in left subtree.
           postorderPrint( root->right );   // Print items in right subtree.
           cout << root->item << " ";       // Print the root item.
        }
     } // end postorderPrint()


     void inorderPrint( TreeNode *root ) {
           // Print all the items in the tree to which root points.
           // The items in the left subtree are printed first, followed 
           // by the item in the root node, followed by the items in
           // the right subtree.
        if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
           inorderPrint( root->left );    // Print items in left subtree.
           cout << root->item << " ";     // Print the root item.
           inorderPrint( root->right );   // Print items in right subtree.
        }
     } // end inorderPrint()

output:

 preorderPrint outputs:   1  2  4  5  3  6
       
 postorderPrint outputs:  4  5  2  6  3  1
       
 inorderPrint outputs:    4  2  5  1  3  6

Template:

class T

{

    T(void);

    T(G *pGIn, const unsigned long s, char nIn);

    ~T(void);

    // Member functions

    public:

    bool Expand(const unsigned long newS);

    void Empty(void); private:G *pG;

    char n;

    unsigned long s;

    int f;

    TEntry *p;

};

class TEntry

{// Constructors

    public:

    TEntry();

    TEntry(int l);

// Member functions

    public:

    void Relocate(int delta);

private:// Data members

    int k;TEntry *p;

};

class TEntry

{// Constructors

    public:

    TEntry();

    TEntry(int l);// Member functions

    public:

    void Relocate(int delta);

private: // Data members

    int k;

    TEntry *p;

};

T::T()

{

    p=NULL; s=0; pG=NULL;

    Empty();

    return;

}

T::T(G *pGIn, const unsigned long m, char nIn)

{

    pG=pG; n=nIn;

    return;

}

T::~T(void)

{

    if(p!=NULL)

        delete[] p;

    return;

}

bool T::Expand(const unsigned long newS)

{

    T *pBefore=p;

    p=(T *)_realloc_dbg(p, newS*sizeof(T), _NORMAL_BLOCK,__FILE__,__LINE__);

    s=newS;

    return p!=NULL;

}

void T::Empty()

{

    f=0;

    return;

}

T::T()

{

}

T::T(int i){

k=i;

}

void T::Relocate(int delta){

k+=delta;

return;

}