So I would like help with 3 problems. Problem 1: Consider the definition of a–Tr

Question

So I would like help with 3 problems.

Problem 1: Consider the definition of a–Tree (the one in which each node has at most two children, left, right). Node stores a key value and height of the tree. Provide a suitable ADT (that includes data elements and methods such as constructor, destructor, post order traversals) in c++ with a suitable node structure (with a default and overloaded constructor methods) to represent this tree.
Note: You should just provide the definition of the ADT, you do not have to provide the implementation of any methods except the constructor for the node data structure.

Problem 2: Describe how would you design a queue using two stacks. In particular, how would you define you perform operation for front, enque and dequeue by using stack operations (such as push, pop, top and empty) on these two stacks.                    Note: You don't have to write a code for this. Just describe the process in words.

Problem 3: Provide C++ methods to compute the following in a BST that stores integer values. Prototype of the method is given as below:    

(i) average Value stored in a BST: int avgValue (BinNode *node)    

(ii) Maximum value stored in a BST: int MaxValue (BinNode *node)

Explanation / Answer

Problem 1:

Definition of a–Tree

A tree data structure as a collection of nodes where each node is a data structure contain a value, each node have subnode that called children. a tree can be defined as an ordered tree, with a value assigned to each node. Tree actually represented as a data structure that has list of nodes and an adjacency list of edges between nodes,

If we search for a tree which each node has at most two children, left, right that called binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of containers: data structures that store number and value of any item.

struct node{

  int data;

  struct node* left;

  struct node* right;

  struct node* nextRight;

}

If we talk about B-tree that is a tree data structure that keeps data sorted and allows all operations like searches, insertions, and deletions. The B-tree is a generalization of a binary search tree in that a node can have more than two children .Each internal node of a B-tree will contain a number of keys. The keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: x1and x2. All values in the leftmost subtree will be less than x1, all values in the middle subtree will be between x1 and x2, and all values in the rightmost subtree will be greater than x2.

B-trees contain height and key value that number of keys within each internal node, the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing of the tree occurs less often. The maximum number of child nodes depends on the information that must be stored for each child node and the size of a full disk block or an analogous size in secondary storage.

ADT

A useful tool for specifying the logical properties of a data type is the abstract data type or ADT.It's basic mathematical concept that defines the data type. An ADT consists of two parts:- a value definition and an operator definition. The value definition defines the collection of values for the ADT and consists of two parts: a definition clause and a condition clause.

// Binary tree node abstract class
template <typename E> class BinNode
{
public:
virtual ˜BinNode()
{

} // Base destructor
// Return the node’s value
virtual E& element() = 0;

// Set the node’s value
virtual void setElement(const E&) = 0;

// Return the node’s left child
virtual BinNode* left() const = 0;

// Set the node’s left child
virtual void setLeft(BinNode*) = 0;

// Return the node’s right child
virtual BinNode* right() const = 0;

// Set the node’s right child
virtual void setRight(BinNode*) = 0;

// Return the post order traversals
virtual BinNode* Post_Traverse() const = 0;

// Set the node’s right child
virtual void setPost_Traverse(BinNode*) = 0;

// Return true if the node is a leaf, false otherwise
virtual bool isLeaf() = 0;
};

Problem 2

According to declaration above, a queue need to implement by 2 stack so we take 2 stack name as stack1 and stack2.Now queue follows the rule “First In First Out” with two stacks follow the rule of “First In Last Out”.Now we have 2 different situation just opposite to each other.so we can take stack 1 as usable and stack2 as temperary.

Now let insert {a,b,c} in stack1 so as stack rule "“First In Last Out" first a element will go in stack1 then b and then c.It will show

Then if we put all this element in queue need to follow rule "First In First Out".but now we have opposite situation so here we will use stack2 .now we put element in stack2 it will go like {c,b,a}.

Now we can pop stack 2 element a and insert into queue.Now stack2 have element {c,b}.Then again need to follow same procedure.Pop element from stack2 and push into stack1.now b will come and push into stack 2 then next push C.

Stack1 = {b,c}

Here b is in top so pop b from stack1 and insert into queue again go to stack1 pop last element c and push into queue.

template <typename T> class Queue
{
public:
    Queue(void);

void Tail(const T& node);
    T deleteHead();               

private:
    stack<T> stack1;
    stack<T> stack2;
};

template<typename T> void Queue<T>::Tail(const T& element)
{
    stack1.push(element);
}

template<typename T> T Queue<T>::deleteHead()
{
    if(stack2.size()<= 0)
    {
        while(stack1.size()>0)
        {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }

    if(stack2.size() == 0)
        throw new exception("queue is empty");

    T head = stack2.top();
    stack2.pop();

    return head;
}

Problem 3

(i) average Value stored in a BST: int avgValue (BinNode *node)    

int avgValue (BinNode *node)
{
if (node == nullptr)
   return 0;
        
     int sum = avg(node->left) + avg(node->right) + node->value;
   
    if(node->left && node->right)
    {
      return sum/3;
     }
    else
    if(!node->left && !node->right)
    {
    return sum;
    }
    else
    return sum/2;
}

ii) Maximum value stored in a BST: int MaxValue (BinNode *node)

int MaxValue (BinNode *node)
{
    if (node == nullptr)
        return 0;

    int max = node->data;
  
        if(node->left != nullptr) {
            int leftMax = MaxValue(node->left);
            if(max < leftMax)
                max = leftMax;
        }
  
        if(node->right != nullptr) {
            int rightMax = MaxValue(node->right);
            if(max < rightMax)
                max = rightMax;
        }
  
        return max;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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