Plz help out the with the below mentioned problem (Query by Someone else, i
was not able to understand)
Building a Binary tree with XOR
Hi All,
Before starting any binary tree problem I will be creating such kind
of binary tree and will be solving that problem accordingly.
>From the last few days I am trying to code to build a binary tree with
"Exclusive Operators". Here I am trying to build the tree in the level
order way like all the elements will be placed in the queue in the
order of levels so that the final binary tree will be almost complete
binary tree.
In general the left node will contain the left side tree adress
details and right node will contain the right tree details.
But the XOR Binary trees will be holding the XOR values of parent and
left child in the left node and in the same way the parent and right
child will be in the right part.
Here I am unable to track the "parent" of a particular node after the
level 3. Does it possible to create a XOR binary tree with the level
order mechanism. If possible, could you provide me clues in resolving
this problem.
My files looks like as below
Header file:
--------------------------------
#include<iostream>
#include<queue>
using namespace std;
typedef unsigned long pointer;
struct BTXNode
{
int data;
struct BTXNode* fleft;
struct BTXNode* fright;
};
class BTX
{
struct BTXNode *root;
public:
BTX()
{
root=NULL;
}
struct BTXNode* getNode(int data);
int insertAtLeaf(struct BTXNode* node);
};
------------------------------------------
CPP file
-------------------------------
#include "btf_xor.h"
struct BTXNode* BTX::getNode(int data)
{
struct BTXNode* node=new BTXNode();
node->data=data;
node->fleft=NULL;
node->fright=NULL;
return node;
}
int BTX::insertAtLeaf(struct BTXNode* nd)
{
cout<<"insertAtLeaf"<<" Data is "<<nd->data<<endl;
bool set_ind=true;
bool right_ind=false;
struct BTXNode *parent=NULL;
if(!root)
{
root=nd;
return 1;
}
queue<BTXNode*> q;
q.push(root);
q.push(NULL);
while(!q.empty() && set_ind)
{
struct BTXNode *temp=q.front();
q.pop();
if(temp)
{
cout<<"temp->data is"<<temp->data<<endl;
if(temp->fleft != parent)
{
struct BTXNode* left=(struct BTXNode*)((pointer)temp-
>fleft^(pointer)parent);
q.push(left);
right_ind=true;
}
else
{
nd->fleft=(struct BTXNode*)((pointer)temp ^
(pointer)nd->fleft);
nd->fright=(struct BTXNode*)((pointer)temp ^
(pointer)nd->fright);
//temp->fleft=(struct BTXNode*)((pointer)nd ^
(pointer)parent);
temp->fleft=(struct BTXNode*)((pointer)nd ^
(pointer)temp->fleft);
right_ind=false;
set_ind=false;
}
if(right_ind)
{
if(temp->fright != parent)
{
struct BTXNode* right=(struct BTXNode*)((pointer)temp-
>fright^(pointer)parent);
q.push(right);
right_ind=true;
}
else
{
nd->fright=(struct BTXNode*)((pointer)temp ^
(pointer)nd->fright);
nd->fleft=(struct BTXNode*)((pointer)temp ^
(pointer)nd-
>fleft);
//temp->fright=(struct BTXNode*)((pointer)nd ^
(pointer)parent);
temp->fright=(struct BTXNode*)((pointer)nd ^
(pointer)temp-
>fright);
set_ind=false;
}
}
parent=temp;
}
else
{
if(!q.empty())
{
q.push(NULL);
}
}
}
}
int main()
{
BTX btx;
btx.insertAtLeaf(btx.getNode(10) );
btx.insertAtLeaf(btx.getNode(8));
btx.insertAtLeaf(btx.getNode(12));
btx.insertAtLeaf(btx.getNode(7));
btx.insertAtLeaf(btx.getNode(9));
btx.insertAtLeaf(btx.getNode(11));
btx.insertAtLeaf(btx.getNode(13));
return 0;
}
----------------------------------------
Regards
Sunil
--
Regards
Ravi Maggon
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
