Hi, I\'m supposed to set up a LinkedBinaryTree class and create a simple test dr

Question

Hi, I'm supposed to set up a LinkedBinaryTree class and create a simple test driver to perform basic operations on a binary tree of a string of names. Given the header file for this problem where the struct Node is a protected member, how does one access these private members to be able to read/write data into? More so, how does one construct the object in the test driver, then access the nodes and do other basic operations?

Thanks in advance,

Chris

----------------------------------------------------------------------------------------------------------------------------------------------------------------

Code with syntax highlighting link: http://pastebin.com/FvTuJEGF

Code of header file is listed below:

#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H
#include <iostream>
#include <list>

typedef int Elem;                   // base element type
class LinkedBinaryTree {
protected:
   struct Node {                   // a node of the tree
       Elem elt;                   // element value
       Node* par;                   // parent
       Node* left;                   // left child
       Node* right;                   // right child
       Node() : elt(), par(NULL), left(NULL), right(NULL) { } // constructor
   };
public:
   class Position {                   // position in the tree
   private:
       Node* v;                       // pointer to the node
   public:
       Position(Node* _v = NULL) : v(_v) { }       // constructor
       Elem& operator*()                   // get element
       {
           return v->elt;
       }
       Position left() const               // get left child
       {
           return Position(v->left);
       }
       Position right() const               // get right child
       {
           return Position(v->right);
       }
       Position parent() const               // get parent
       {
           return Position(v->par);
       }
       bool isRoot() const               // root of the tree?
       {
           return v->par == NULL;
       }
       bool isExternal() const               // an external node?
       {
           return v->left == NULL && v->right == NULL;
       }
       friend class LinkedBinaryTree;           // give tree access
   };
   typedef std::list<Position> PositionList;       // list of positions

public:
   LinkedBinaryTree();                   // constructor
   int size() const;                   // number of nodes
   bool empty() const;                   // is tree empty?
   Position root() const;               // get the root
   PositionList positions() const;             // list of nodes
   void addRoot();                   // add root to empty tree
   void expandExternal(const Position& p);       // expand external node
   Position removeAboveExternal(const Position& p);   // remove p and parent
   // housekeeping functions omitted...
protected:                        // local utilities
   void preorder(Node* v, PositionList& pl) const;   // preorder utility
private:
   Node* _root;                   // pointer to the root
   int n;                       // number of nodes
};

LinkedBinaryTree::LinkedBinaryTree()
   : _root(NULL), n(0) { }

int LinkedBinaryTree::size() const               // return number of nodes
{
   return n;
}

bool LinkedBinaryTree::empty() const
{
   return size() == 0;
}

LinkedBinaryTree::Position LinkedBinaryTree::root() const
{
   return Position(_root);
}

void LinkedBinaryTree::addRoot()
{
   _root = new Node;
   n = 1;
}

// list of all nodes
LinkedBinaryTree::PositionList LinkedBinaryTree::positions() const {
   PositionList pl;
   preorder(_root, pl);                   // preorder traversal
   return PositionList(pl);               // return resulting list
}

void LinkedBinaryTree::expandExternal(const Position& p)
{
   Node* v = p.v;                  
   v->left = new Node;
   v->left->par = v;
   v->right = new Node;
   v->right->par = v;
   n += 2;
}

LinkedBinaryTree::Position LinkedBinaryTree::removeAboveExternal(const Position& p)
{
   Node* w = p.v; Node* v = w->par;
   Node* sib = (w == v->left ? v->right : v->left);
   if (v == _root) {
       _root = sib;
       sib->par = NULL;
   }
   else {
       Node* gpar = v->par;
       if (v == gpar->left) gpar->left = sib;
       else gpar->right = sib;
       sib->par = gpar;
   }
   delete w; delete v;
   n -= 2;
   return Position(sib);
}

// preorder traversal
void LinkedBinaryTree::preorder(Node* v, PositionList& pl) const {
   pl.push_back(Position(v));               // add this node
   if (v->left != NULL)                   // traverse left subtree
       preorder(v->left, pl);
   if (v->right != NULL)                   // traverse right subtree
       preorder(v->right, pl);
}

#endif

Explanation / Answer

#include <iostream>
#include <string>
#include <queue>
using namespace std;

// Linked list node
struct ListNode
{
    int data;
    ListNode* next;
};

// Binary tree node structure
struct BinaryTreeNode
{
    int data;
    BinaryTreeNode *left, *right;
};

// Function to insert a node at the beginning of the Linked List
void push(struct ListNode** head_ref, int new_data)
{
    // allocate node and assign data
    struct ListNode* new_node = new ListNode;
    new_node->data = new_data;

    // link the old list off the new node
    new_node->next = (*head_ref);

    // move the head to point to the new node
    (*head_ref)    = new_node;
}

// method to create a new binary tree node from the given data
BinaryTreeNode* newBinaryTreeNode(int data)
{
    BinaryTreeNode *temp = new BinaryTreeNode;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// converts a given linked list representing a complete binary tree into the
// linked representation of binary tree.
void convertList2Binary(ListNode *head, BinaryTreeNode* &root)
{
    // queue to store the parent nodes
    queue<BinaryTreeNode *> q;

    // Base Case
    if (head == NULL)
    {
        root = NULL; // Note that root is passed by reference
        return;
    }

    // 1.) The first node is always the root node, and add it to the queue
    root = newBinaryTreeNode(head->data);
    q.push(root);

    // advance the pointer to the next node
    head = head->next;

    // until the end of linked list is reached, do the following steps
    while (head)
    {
        // 2.a) take the parent node from the q and remove it from q
        BinaryTreeNode* parent = q.front();
        q.pop();

        // 2.c) take next two nodes from the linked list. We will add
        // them as children of the current parent node in step 2.b. Push them
        // into the queue so that they will be parents to the future nodes
        BinaryTreeNode *leftChild = NULL, *rightChild = NULL;
        leftChild = newBinaryTreeNode(head->data);
        q.push(leftChild);
        head = head->next;
        if (head)
        {
            rightChild = newBinaryTreeNode(head->data);
            q.push(rightChild);
            head = head->next;
        }

        // 2.b) assign the left and right children of parent
        parent->left = leftChild;
        parent->right = rightChild;
    }
}

// Utility function to traverse the binary tree after conversion
void inorderTraversal(BinaryTreeNode* root)
{
    if (root)
    {
        inorderTraversal( root->left );
        cout << root->data << " ";
        inorderTraversal( root->right );
    }
}

// Driver program to test above functions
int main()
{
    // create a linked list shown in above diagram
    struct ListNode* head = NULL;
    push(&head, 36); /* Last node of Linked List */
    push(&head, 30);
    push(&head, 25);
    push(&head, 15);
    push(&head, 12);
    push(&head, 10); /* First node of Linked List */

    BinaryTreeNode *root;
    convertList2Binary(head, root);

    cout << "Inorder Traversal of the constructed Binary Tree is: ";
    inorderTraversal(root);
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.