Question

You are given a class TNode that contains one integer value, and three pointers -one to the parent, one to the left child, and one to the right child. You need to complete the class BTree and two other functions specified in the cpp file Task 1: Write a function isValidBT that given inputs as a binary tree in the array form, and outputs whether the array forms a correct binary tree. The inputs contain a pointer p to an array, and an integer n denoting the mmber of slots used in the array representation. Here the array has size n, and we use plo to store the empty symbol for the binary tree as diseussed in the class. For this representation, the tree has size n-1. Task 2: Implement the constructors (default and copy) of BTree, and the destructor. You need to make sure that the copy constructor makes a separate copy of the list. In addition to the normal copy constructor, here we ask you to implement a special copy constructor that takes input a binary tree of the array form. The inputs have the same format as Task 1, and you need to copy the binary tree, and convert the array form/to the pointer-based construction Task 3: Impleent the function convertpos that takes input an integer position, and returns the TNode pointer that points to the position-th node in the tree. We diseussed about how to do this in the class. Task 4: Implement the add2kft, add2right functions. Tle functionalities are just as the names. Here you need to consider how to handle different input of positious, ie. places that you want to add the node/tree to. You need to consider whether the position is available to add a new node Task 5: Write the removeleaf function. You need to first check whether the input is a leaf or not If that is a leaf, then remove it. Otherwise do nothing. Task 6: Write a function Toarray that converts the BTree into the array form You can start by determining the size to the reference n, and new an array of size n. Then you need to produce the correct array according to your BTree. Task 7: Write sapnodes and the three tree traversal algorithms. For the traversal algorithm, you can just print the notes according to the order, Here you just need to swap the values for the swapnodes. This task should be very simple. Task 8: Write a function isValidBST that checks whether the binary tree is a valid binary search tree. Task 9: Test the above tasks.
#include<iostream>

using namespace std;


class TNode
{
public:
int val;
TNode(){}
TNode(int v){val = v;}
TNode * left;
TNode * right;
TNode * parent;
};



class BTree
{
public:

//constructors and destructor
BTree();
BTree(TNode *r);// initialize BTree with the root r. r is the only node.

BTree(const BTree & t); // copy constructor
BTree(const int *p, const int n);// similar to the copy constructor, but your input is of the array form.
// input is given an array that denotes a tree that uses up to n slots. The size of the tree is not given directly as input.
// the array is pointed by p and has size n, where p[0] is used to store the empty symbol.
//the function converts the array representation into a linked-list representation, i.e. BTree
  

  
~BTree();
  
int size;
TNode *root;
  
TNode * convertpos(int position);// find the pointer where the position points to

void add2left(TNode newnode, TNode *p); // you should new a node that copies newnode and then add to left of p

void add2right(TNode newnode, TNode *p);
  
void add2left(TNode newnode, int position);
void add2right(TNode newnode, int position);

  
void add2left(BTree newsubtree, int position); // you should create a separate new tree that copies
//newsubtree and then add to left of p

void add2right(BTree newsubtree, int position);
  
  
void removeleaf(int position); // should check if position is leaf

void removeleaf(TNode *p);
  
void swapnodes(TNode *n1, TNode *n2); //swap-the-values is fine
  
int * Toarray(int &n); // convert the BT into the array form. Determine what n should be, and new an array of size n+1, and store the empty symbol at array[0]. Convert the BT into the array form and retrun the array pointer. The size of the array will be given to the variable n.
  
void print_pre_order(); // print the node as you traverse according to the order.

void print_in_order();
void print_post_order();
bool isValidBST(); // return whether this BT is a valid BST
};


bool isValidBT(const int *p, const int n);
//Determine whether the array forms a valid BT.
// the input format is the same as the above



int main()
{
return 0;
}
0 0
Add a comment Improve this question Transcribed image text
Answer #1

#include<iostream>
#include<vector>

using namespace std;

class TNode
{

    public:

        int val;
        TNode():
            val    (-9999),
            left   (NULL) ,
            right (NULL) ,
            parent (NULL)
            {}

        TNode(int v):
            val    (v),
            left   (NULL),
            right (NULL),
            parent (NULL)
            {}

        bool is_valid() {

            if ( this->left && this->right )
                return true;

            return false;
        }

        TNode * left;
        TNode * right;
        TNode * parent;
};

class BTree
{
    vector<int> m_data;

    // [inner] return lowest element
   TNode* m_tree_min(TNode *T)
    {
       TNode *x = T;
        while (x->left != NULL)
            x = x->left;
        return x;
    }

    // [inner] return tree successor
   TNode* m_tree_successor(TNode*x)
    {
       TNode *y;
        if (x->right != NULL)
            return m_tree_min(x->right);
        else
        {
            y = x->parent;
            while (y != NULL && x == y->right)
            {
                x = y;
                y = y->parent;
            }
        }

        return y;
    }

    // [inner] transplant a node
    void m_tree_transplant(TNode *&T, TNode *z, TNode *y)
    {
        if (z->parent == NULL)
            T = y;
        else
        {
            if (z->parent->left == z)
                z->parent->left = y;
            else
                z->parent->right = y;
        }

        if (y != NULL)
            y->parent = z->parent;
    }

    // [inner] deleter
    void m_tree_delete(TNode *&T, TNode *z)
    {
        TNode *y;
        TNode *s = z->parent;
        if (z->left == NULL)
            m_tree_transplant(T, z, z->right);
        else
        {
            if (z->right == NULL)
                m_tree_transplant(T, z, z->left);
            else
            {
                y = m_tree_successor(z);
                s = y->parent;
                if (y != z->right)
                {
                    m_tree_transplant(T, y, y->right);
                    y->right = z->right;
                    y->right->parent = y;
                }
                    y->left = z->left;
                    y->left->parent = y;
                    m_tree_transplant(T, z, y);
            }
        }

        delete z;
    }

    // print in order [ LEFT, ROOT, RIGHT ]
    void m_in_order( TNode* node, bool print_to_arr=false)
    {
        if ( node ) {

            /* first recur on left child */
            if(node->left) {
               m_in_order(node->left, print_to_arr);
            }

            // print to arr
            if( print_to_arr ) {

                this->m_data.push_back( node->val );

            // or print to cout
            } else {

                /* then print the data of node */
                cout << " " << node->val << " ";
            }

            /* now recur on right child */
            if(node->right) {
                m_in_order(node->right, print_to_arr);
            }
        }
    };

    // print post order [ LEFT, ROOT, RIGHT ]
    void m_post_order( TNode* node)
    {
        if ( node ) {

            /* first recur on left child */
            if(node->left) {
               m_post_order(node->left);
            }

            /* now recur on right child */
            if(node->right) {
                m_post_order(node->right);
            }

            /* then print the data of node */
            cout << " " << node->val << " ";

        }
    };

    // print pre order [ ROOT , LEFT, RIGHT ]
    void m_pre_order( TNode* node)
    {
        if ( node ) {

            /* then print the data of node */
            cout << " " << node->val << " ";

            /* first recur on left child */
            if(node->left) {
               m_pre_order(node->left);
            }

            /* now recur on right child */
            if(node->right) {
                m_pre_order(node->right);
            }

        }
    };

    // [inner] m_tree_search search & return the node ( if exist )
    TNode* m_tree_search(TNode *T, int k)
    {
        TNode *x = T;
        while (x != NULL && x->val != k)
        {
            if (x->val > k)
                x = x->left;
            else
                x = x->right;
        }
        return x;
    };

    // [inner] m_get_size compute size
    int m_get_size(TNode *node)
    {
        if (node==NULL)
            return 0;
        else
            return(m_get_size(node->left) + 1 + m_get_size(node->right));
    };

    // [inner] insert a new key
    void m_tree_insert(TNode *&T, int key)
    {
        TNode* new_node = new TNode(key);

        cout << " *** insert key [" << new_node->val << "]" << endl ;

        // y = parent, if any
        // x = current element
        TNode *y = NULL, *x = T;

        //
        while (x != NULL)
        {
            //cout << " try to locate " << endl;
            y = x;

            // search on left
            if (new_node->val < x->val) {

                x = x->left;

            // search on right
            } else
            if (new_node->val > x->val)
            {

                x = x->right;

            // node exists ..
            } else {

               cout << "    value already in tree, exit .. " << endl;
               delete new_node;
               return;
            }

        }

        // Y can be NULL [ we have root element in this case ]
        new_node->parent = y;
        if (y == NULL) {

            cout << "    [ROOT] added (tree size = 1)" << endl;
            T = new_node;
            this->size = 1;
        }
        else
        {
            //bool is_insert = false;

            if (new_node->val < y->val) {

                (this->size)++ ;

                cout << "    value inserted as left of [" << y->val << "] new size = " << this->size << endl;
                y->left = new_node;
            }
            else
            if (new_node->val > y->val) {

                (this->size)++ ;

                cout << "    value inserted as right of [" << y->val << "] new size = " << this->size << endl;
                y->right = new_node;

            // node exists ..
            } else {

                cout << "    value already in tree, exit .. " << endl;
                delete new_node;
                return;
            }
        }
    }

    // [inner] destroy all sub nodes ..
    void m_destroyTree (TNode* node)
    {
        //cout << " *** delete tree " << endl ;
        if ( NULL == node )
            return;

        if(node->right) {
            if(node->right->right || node->right->left){
                m_destroyTree(node->right);
            } else {

                (this->size)-- ;
                cout << " *** delete node " << node->right->val << " new size : " << this->size << endl ;
                delete node->right;
            }
        }
        if(node->left) {
            if(node->left->left || node->left->right){
                m_destroyTree(node->left);
            } else {

                (this->size)-- ;
                cout << " *** delete node " << node->left->val << " new size : " << this->size << endl ;
                delete node->left;
            }
        }

        (this->size)-- ;
        cout << " *** delete node " << node->val << " new size : " << this->size << endl ;
        delete node;
    };

    // [inner] copy node [recursive]
    TNode* m_copy_node(const TNode *aCopy) {

        if (aCopy == NULL)
            return NULL;

        TNode *copyNode = new TNode(aCopy->val    );
        copyNode->left   = m_copy_node(aCopy->left );
        copyNode->right = m_copy_node(aCopy->right );
        return copyNode;
    }

    public:

        // size of tree .. [ updated on delete & insert ]
        int size;

        // tree root
        TNode *root;

        // empty symbol flag
        int empty_symbol;

        //constructors and destructor
        BTree():
            root         ( NULL ),
            empty_symbol ( -9999 ),
            size         ( 0     )
        {};

        // initialize BTree with the root r. r is the only node.
        BTree(TNode *r):
            root ( NULL ),
            empty_symbol ( -9999 )
        {
            this->root = this->m_copy_node( r );
            this->size = this->m_get_size( this->root );
        };

        // copy constructor
        BTree(const BTree& aOther)
        {
            this->size         = aOther.size         ;
            this->empty_symbol = aOther.empty_symbol ;
            this->root = this->m_copy_node(aOther.root);
        };

        // similar to the copy constructor, but your input is of the array form.
        // input is given an array that denotes a tree that uses up to n slots. The size of the tree is not given directly as input.
        // the array is pointed by p and has size n, where p[0] is used to store the empty symbol.
        // the function converts the array representation into a linked-list representation, i.e. BTree
        BTree(const int *p, const int n):
            root         ( NULL ),
            empty_symbol ( -9999 ),
            size         ( 0     )
        {
            //cout << " *** tree values *** " << endl;
            for ( int i = 0; i < n ; i++ ) {

                //cout << " " << *p++ ;

                // empty simbol
                if ( 0 == i ) {

                     this->empty_symbol = *p;

                } else {

                    // always insert in root
                    this->m_tree_insert( this->root, *p);
                }

                p++;
            }

            //cout << endl ;
        };

        // destructor
        ~BTree()
        {
            cout << "~BTree()" << endl ;

            // dealocate memory
            this->m_destroyTree( this->root );

            // reset inner data to defaults
            this->root         = NULL ;
            this->empty_symbol = -9999 ;
            this->size         = 0     ;
        };

        // find the pointer where the position points to
        TNode* convertpos(int position)
        {
            TNode* node = this->m_tree_search(this->root, position);

            if (node)
                cout << " *** search: " << position << " exists in tree " << endl ;
            else
                cout << " *** search: " << position << " no such key " << endl ;

            return node; // this is null if node not located in tree
        }

        void add2left(TNode *newnode, TNode *p)
        {
            if ( p && newnode )
                p->left = newnode;
        }

        void add2right(TNode *newnode, TNode *p)
        {
            if ( p && newnode )
                p->right = newnode;
        }

        void add2left(TNode *newnode, int position)
        {
            TNode* p = this->m_tree_search(this->root, position);
            this->add2left(newnode, p);
        }

        void add2right(TNode *newnode, int position)
        {
            TNode* p = this->m_tree_search(this->root, position);
            this->add2right(newnode, p);
        }

        void add2left(BTree *newsubtree, int position)
        {
            TNode* p = this->m_tree_search(this->root, position);

            if ( p && newsubtree && newsubtree->root )
                p->left = newsubtree->root;
        }

        void add2right(BTree *newsubtree, int position)
        {
            TNode* p = this->m_tree_search(this->root, position);

            if ( p && newsubtree && newsubtree->root )
                p->right = newsubtree->root;
        }

        // remove a no by position
        void removeleaf(int position)
        {
            cout << " *** delete position [" << position << "] " << endl ;

            TNode* node = this->m_tree_search(this->root, position);

            if ( node && node->parent /* delete root is not supported */ ) {

                //int node_size = m_get_size( node );

                //cout << " *** deleted [" << node_size << "] elements " << endl ;
                this->m_tree_delete( this->root, node );

                return;
            }

            cout << "    deleted [0] elements, key not in tree [" << position << "] " << endl ;

        }

        // remove a node by pointer ..
        void removeleaf(TNode *p)
        {
            if ( p )
                this->removeleaf( p->val );
        }

        //swap-the-values is fine
        void swapnodes(TNode* n1, TNode *n2)
        {
            // null check for both ..
            if ( n1 && n2 ) {

                int tmp = n1->val;
                n1->val = n2->val;
                n2->val = tmp;
            }
        }

        // convert the BT into the array form.
        // Determine what n should be, and new an array of size n+1,
        // and store the empty symbol at array[0].
        // Convert the BT into the array form and return the array pointer.
        //The size of the array will be given to the variable n.
        int* toarray(int &n)
        {
            this->m_data.clear();

            this->m_data.push_back( this->empty_symbol );
            this->m_in_order( this->root, true /*print_to_arr*/ );

            n = (int)this->m_data.size();

            //cout << " *** sz = " << n << endl ;

            return &this->m_data[0]; // return the inner array
        }

        // pre_order traversing (Root, Left, Right)
        void print_pre_order()
        {
            cout << " print [pre order] (Root, Left, Right) " << endl;
            this->m_pre_order( this->root );
            cout << endl;
        };

        // in_order traversing (Left, Root, Right)
        void print_in_order()
        {
            cout << " print [in order] (Left, Root, Right)" << endl;
            this->m_in_order( this->root );
            cout << endl;
        };

        // post_order traversing (Left, Right, Root)
        void print_post_order()
        {
            cout << " print [post order] (Left, Right, Root) " << endl;
            this->m_post_order( this->root );
            cout << endl;
        };

        // return whether this BT is a valid BST
        bool isValidBST() {

            if ( this->root && (this->size > 0))
                return true;
            else
                return false;
        }

};

// Determine whether the array forms a valid BT.
// the input format is the same as the above
bool isValidBT(const int *p, const int n)
{
    // check p is not NULL and first value is 0
    if ( p && (*p == 0) )
        return true;

    return false;
}

int main()
{
    // declare our array of integers:
    int tree_values[] = {0/*empty symbol*/, 16, 2, 77, 29};

    cout << endl << "tree_1 init with values : {0/*empty symbol*/, 16, 2, 77, 29}" << endl ;
    BTree tree_1 = BTree(tree_values, 5 );

    cout << endl << "tree_1 : print_in_order" << endl ;
    tree_1.print_in_order();

    cout << endl << "tree_2 : Copy C-tor -> object" << endl ;
    BTree tree_2 = BTree( tree_1 );

    cout << endl << "tree_3 : Copy C-tor -> pointer" << endl ;
    BTree tree_3 = BTree( tree_1.root );

    cout << endl << "tree_1 : print_in_order" << endl ;
    tree_3.print_in_order   ();

    cout << endl << "tree_1.removeleaf(2) " << endl ;
    tree_1.removeleaf(2);

    cout << endl << "tree_1 : print_in_order" << endl ;
    tree_1.print_in_order   ();

    cout << endl << "tree_2 : print_in_order" << endl ;
    tree_2.print_in_order   ();

    cout << endl << "tree_2 : toarray() -> print values " << endl ;

    int n = -1;
    int* arr = tree_2.toarray(n);

    cout << endl << endl ;
    for ( int i = 0; i < n ; i++ ) {
        cout << " [" << *arr++ << "] ";
    }

    cout << endl << endl << " testing swap " << endl ;

    TNode* p_77 = tree_1.convertpos( 77 );
    TNode* p_29 = tree_1.convertpos( 29 );

    cout << endl ;
    if ( p_77 && p_29 ) {

        cout << " p_77->val = " << p_77->val << " , p_29->val = " << p_77->val << endl ;

        tree_1.swapnodes(p_77, p_29);

        cout << " p_77->val = " << p_77->val << " , p_29->val = " << p_77->val << endl ;
    }

    cout << endl << " testing is isValidBST() " << endl ;
    cout << endl << "is_valid_bst tree_1             : " << ( tree_1.isValidBST() ? "TRUE" : "FALSE" ) ;

    BTree empty_tree = BTree();

    cout << endl << "is_valid_bst new tree (no data) : " << ( empty_tree.isValidBST() ? "TRUE" : "FALSE" ) ;

    cout << endl << endl ;
    return 0;

}


CAUsersisowmi\Desktop\Projectl.exe tree-l in it with values : {0/жетрty symbol,</, 16, 2, 77, 293 *insert key [161 *insert ke

Add a comment
Know the answer?
Add Answer to:
#include<iostream> using namespace std; class TNode { public: int val; TNode(){} TNode(int v){val = v;} TNode...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Class BTree { private: int size; Node* root; public: // constructors BTree() : root(nullptr), siz...

    class BTree { private: int size; Node* root; public: // constructors BTree() : root(nullptr), size(0) {} // default constructor BTree(const BTree& other); // copy constructor BTree(BTree&& other); // move constructor BTree& operator=(const BTree& other); BTree& operator=(BTree&& other);    }; Implement the following function BTree& BTree::operator=(BTree&& other) { if (this != &other) { } return *this; } Can you implement the move assigment and the move constructor

  • #include <iostream> #include <cstddef> using std::cout; using std::endl; class Node { int value; public: Node* left;...

    #include <iostream> #include <cstddef> using std::cout; using std::endl; class Node { int value; public: Node* left; // left child Node* right; // right child Node* p; // parent Node(int data) { value = data; left = NULL; right = NULL; p = NULL; } ~Node() { } int d() { return value; } void print() { std::cout << value << std::endl; } }; int main(int argc, const char * argv[]) { } function insert(Node *insert_node, Node *tree_root){ //Your code here...

  • C++ LinkedList I need the code for copy constructor and assignment operator #include <iostream> #include <string> using namespace std; typedef string ItemType; struct Node {    ItemType va...

    C++ LinkedList I need the code for copy constructor and assignment operator #include <iostream> #include <string> using namespace std; typedef string ItemType; struct Node {    ItemType value;    Node *next; }; class LinkedList { private:    Node *head;    // You may add whatever private data members or private member functions you want to this class.    void printReverseRecursiveHelper(Node *temp) const; public:    // default constructor    LinkedList() : head(nullptr) { }    // copy constructor    LinkedList(const LinkedList& rhs);    // Destroys all the dynamically allocated memory    //...

  • #code for creature.cpp #include <iostream> using namespace std; class Creature { public: Creature(); void run() const;...

    #code for creature.cpp #include <iostream> using namespace std; class Creature { public: Creature(); void run() const; protected: int distance; }; Creature::Creature(): distance(10) {} void Creature::run() const { cout << "running " << distance << " meters!\n"; } class Wizard : public Creature { public: Wizard(); void hover() const; private: int distFactor; }; Wizard::Wizard() : distFactor(3) {} void Wizard::hover() const { cout << "hovering " << (distFactor * distance) << " meters!\n"; } //Created new derived class from Creature class Widget...

  • #ifndef PROCESSREQUESTRECORD_CLASS #define PROCESSREQUESTRECORD_CLASS #include <iostream> #include <string> using namespace std; class procReqRec { public: //...

    #ifndef PROCESSREQUESTRECORD_CLASS #define PROCESSREQUESTRECORD_CLASS #include <iostream> #include <string> using namespace std; class procReqRec { public: // default constructor procReqRec() {} // constructor procReqRec(const string& nm, int p); // access functions int getPriority(); string getName(); // update functions void setPriority(int p); void setName(const string& nm); // for maintenance of a minimum priority queue friend bool operator< (const procReqRec& left, const procReqRec& right); // output a process request record in the format // name: priority friend ostream& operator<< (ostream& ostr, const procReqRec&...

  • C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int...

    C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int data) { this->data=data; this->next = 0; } int getData(){return data;} Node* getNext(){return next;} void setNext(Node* next){this->next=next;} }; class LinkedList { private: Node* head = 0; public: int isEmpty() {return head == 0;} void print() { Node* currNode = head; while(currNode!=0) { cout << currNode->getData() << endl; currNode = currNode->getNext(); } } void append(int data) {...

  • #include <iostream> using namespace std; int main(void) {    int SIZE;    cout<<"Enter the size of the...

    #include <iostream> using namespace std; int main(void) {    int SIZE;    cout<<"Enter the size of the array"<<endl;    cin>>SIZE;     int *numlist = new int[SIZE];     // Read SIZE integers from the keyboard     for (int i = 0; i<SIZE; i++ )    {        cout << "Enter value #" << i+1 << ": ";        cin >> numlist[i];     }     // Display the numbers in a reverse order     for (int i = SIZE; i > 0; i--...

  • // PLACE YOUR NAME HERE #include <iostream> using namespace std; float findAverage (int [], int); //...

    // PLACE YOUR NAME HERE #include <iostream> using namespace std; float findAverage (int [], int); // finds average of all //grades int findHighest (int [], int); // finds highest of all //grades int findFirstFail( int[]); int main() { int grades[100]; // the array holding 100 grades. int numberOfGrades; // the number of grades read. int pos; // index to the array. float avgOfGrades; // contains the average of the grades. int highestGrade; // contains the highest grade. int inderOfFail; //...

  • Please help me with FLOWCHART and UML diagram for class, thank you! #include <iostream> #include <fstream>...

    Please help me with FLOWCHART and UML diagram for class, thank you! #include <iostream> #include <fstream> #define MAX 10 using namespace std; class WordListTree { public:    // Structure of a node    struct Node {        string key;        // Create an array of up to MAX children        Node* child[MAX];    };    // Create a tree of strings    Node* newNode(string key) {        Node* temp = new Node;        (*temp).key =...

  • USING THIS CODE: #include <iostream> #include <string> using namespace std; class Contact { //this class cannot...

    USING THIS CODE: #include <iostream> #include <string> using namespace std; class Contact { //this class cannot be viewed from outside of the private class. //only the class functions within the class can access private members. private: string name; string email; string phone; //the public class is accessible from anywhere outside of the class //however can only be within the program. public: string getName() const { return name; } void setName(string name) { this->name = name; } string getEmail() const {...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
Active Questions
ADVERTISEMENT