COMPLETE BINARY TREE :
A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible.
• A complete binary tree of the height h contains between
2h and 2h+1−1 nodes
• A complete binary tree with the n nodes has the height
log2n
• Node positions are specified by the level-order traversal
(the root position is 1)
• If the node is in the position p then:
– the parent node is in the position p/2
– the left child is in the position 2p
– the right child is in the position 2p + 1
Given a set of N nodes, a complete binary tree of these nodes
provides the maximum number of leaves with the minimal average
path length (per node)
The complete binary tree containing n nodes must have at least one
path from root to leaf of length lg[n] log[n]
ALGORITHM FOR COMPLETE BINARY TREE :
First of all, you don't write "algorithms" in C or C++; you write
"programs" (or more granularly, "functions," or more abstractly,
"packages" or "libraries").
Second of all, sure.
struct Tree {
void *Data;
Tree *Left;
Tree *Right;
Tree(void *d, Tree *l, Tree *r): Data(d), Left(l), Right(r) {}
};
struct Tree *my_complete_tree_on_0_levels = NULL;
struct Tree *my_complete_tree_on_1_levels = &Tree(0,0,0);
[Actually, I don't even remember if that '&Tree(...)' is valid
C++. It certainly ought to be. ;-]
Or do you mean "a library to facilitate the creation of complete
binary search trees given *arbitrary* key values"? That's a little
harder! But not so hard that you can't do it yourself, with a little
Googling and a little programming.
The problem you'll run into is that it's very time-consuming to
maintain the "complete tree" invariant. You'll basically have to
re-form the entire tree during each insertion and each deletion,
unless someone's got a really clever algorithm up his sleeve here.
I suggest you look up "AVL rotations" and/or "red-black trees" to
get yourself started, unless for some reason you actually *need*
complete trees, in which case you're stuck with slowness, AFAIK.
PROGRAM FOR COMPLETE BINARY TREE :
#include <iostream.h>
#include <stdlib.h>
enum {TRUE = 1,FALSE = 0};
typedef struct _node
{
int info;
struct _node *left;
struct _node *right;
}node;
class btree
{
private:
node *root;
void InsertLeft(node* & ,node*);
void InsertRight(node* &,node*);
void deltree(node*);
public:
btree();
~btree();
node* GetRoot(void);
void MakeTree(void);
void DeleteNode(node *,node *,int);
int Searchnode(node*,int);
void DisplayTree(node*,int);
void Inorder(node* );
void Preorder(node*);
void Postorder(node*);
};
btree::btree()
{
char create='Y';
root = new node;
cout<<"Enter a number which will become a root"<<endl;
cin>>root->info;
root->left = NULL;
root->right = NULL;
}
btree::~btree()
{
deltree(root);
}
void btree::deltree(node *root)
{
if(root)
{
deltree(root->left);
deltree(root->right);
delete root;
}
}
node* btree::GetRoot(void)
{
return(root);
}
void btree::MakeTree(void)
{
node *newnode;
char create;
do
{
newnode = new node;
cout<<"Enter a number"<<endl;
cin>>newnode->info;
newnode->left=NULL;
newnode->right=NULL;
if(newnode->info < root->info)
InsertLeft(newnode,root);
else
InsertRight(newnode,root);
cout<<"Create another node[y/n]"<<endl;
cin>>create;
}while(create=='Y' || create=='y');
}
void btree::InsertLeft(node* &newnode,node* current)
{
if(current->left==NULL)
current->left=newnode;
else
{
current = current->left;
if(newnode->info < current->info)
InsertLeft(newnode,current);
else
InsertRight(newnode,current);
}
}
void btree::InsertRight(node* &newnode,node* current)
{
if(current->right==NULL)
current->right=newnode;
else
{
current = current->right;
if(newnode->info < current->info)
InsertLeft(newnode,current);
else
InsertRight(newnode,current);
}
}
void btree::DeleteNode(node *current,node *parent,int delnode)
{
if(delnode < current->info)
DeleteNode(current->left,current,delnode);
else if(delnode > current->info)
DeleteNode(current->right,current,delnode);
else if(delnode == current->info)
{
if(current->left == NULL)
{
if(parent->info > current->info)
parent->left = current->right;
else
parent->right = current->right;
}
else if(current->right == NULL)
{
if(parent->info > current->info)
parent->left = current->left;
else
parent->right = current->left;
}
else
{
node *temp;
int flag = 0;
parent = current;
current = current->left;
temp = current;
while(current->right != NULL)
{
current = current->right;
if(flag == 0)
flag = 1;
else
temp = temp->right;
}
parent->info = current->info;
if(flag == 0)
// No right child
parent->left = current->left;
else
temp->right = current->left;
}
delete current;
}
}
int btree::Searchnode(node *current,int num)
{
if(num<current->info && current->left!=NULL)
Searchnode(current->left,num);
else if(num>current->info && current->right!=NULL)
Searchnode(current->right,num);
else
{
if(num==current->info)
return TRUE;
else
return FALSE;
}
return FALSE;
}
void btree::DisplayTree(node *current,int Level)
{
if(current)
{
DisplayTree(current->right,Level+1);
cout<<endl;
for(int i=0;i<Level;i++)
cout<<" ";
cout<<current->info;
DisplayTree(current->left,Level+1);
}
}
void btree::Inorder(node *current)
{
if(current!=NULL)
{
Inorder(current->left);
cout<<current->info;
Inorder(current->right);
}
}
void btree::Preorder(node *current)
{
if(current!=NULL)
{
cout<<current->info;
Preorder(current->left);
Preorder(current->right);
}
}
void btree::Postorder(node *current)
{
if(current!=NULL)
{
Postorder(current->left);
Postorder(current->right);
cout<<current->info;
}
}
void main()
{
int opt;
int num;
char ch='y';
btree bt;
do
{
cout<<"\nEnter your option\n";
cout<<"1. Make a Tree\n";
cout<<"2. Delete a node\n";
cout<<"3. search a node\n";
cout<<"4. display the tree\n";
cout<<"5. Inorder traversal\n";
cout<<"6. preorder traversal\n";
cout<<"7. postorder traversal\n";
cout<<"8. Exit\n";
cin>>opt;
switch(opt)
{
case 1:
bt.MakeTree();
break;
case 2:
int delnode;
cout<<"\nEnter an information to be deleted\n";
cin>>delnode;
bt.DeleteNode(bt.GetRoot(),NULL,delnode);
break;
case 3:
cout<<"\nEnter a number to search in the tree\n";
cin>>num;
if(bt.Searchnode(bt.GetRoot(),num))
cout<<"The number is present"<<endl;
else
cout<<"The number is not present"<<endl;
break;
case 4:
bt.DisplayTree(bt.GetRoot(),1);
break;
case 5:
bt.Inorder(bt.GetRoot());
break;
case 6:
bt.Preorder(bt.GetRoot());
break;
case 7:
bt.Postorder(bt.GetRoot());
break;
case 8:
exit(0);
default:
cout<<"\nInvalid Entry\n";
}
}while(ch=='Y' || ch=='y');
}
