(C++)Implement a member function IsFullTree to test whether the tree is full or

Question

(C++)Implement a member function IsFullTree to test whether the tree is full or not for a class called TreeType.

struct TreeNode
{
ItemType info;
TreeNode* left;
TreeNode* right;
};

//TreeType.h...

#include <string>
#include <fstream>
typedef char ItemType;
struct TreeNode;
#include "QueType.h"
enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};
class TreeType
{
public:
TreeType();                     // constructor
~TreeType();                    // destructor
TreeType(const TreeType& originalTree);
void operator=(const TreeType& originalTree);
// copy constructor
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
int GetLength() const;
int GetHeight() const;
ItemType GetItem(ItemType item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetTree(OrderType order);
ItemType GetNextItem(OrderType order, bool& finished);
void Print(std::ostream& out) const;
void PrettyPrint() const;
void SimplePrettyPrint() const;
private:
TreeNode* root;
QueType preQue;
QueType inQue;
QueType postQue;
};

~     

Explanation / Answer

struct node{
int data;
node *left, *right;
};

void checkcomplete()
{

node *curr = root;
queue<node *> Q;
vector<int> arr;
int lastentry = 0;
Q.push(curr);
int currlevel = 1, nextlevel = 0;
while( currlevel){
node *temp = Q.front();
Q.pop();
currlevel--;
if(temp){
arr.push_back(temp->data);
lastentry = arr.size();
Q.push(temp->left);
Q.push(temp->right);
nextlevel += 2;
}else
arr.push_back(INT_MIN);
if(!currlevel){
currlevel = nextlevel;
nextlevel = 0;
}

}
int flag = 0;
for( int i = 0; i<lastentry && !flag; i++){
if( arr[i] == INT_MIN){
cout<<"Not a complete binary tree"<<endl;
flag = 1;
}
}
if( !flag )
cout<<"Complete binary tree ";
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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