remove duplicates in binary tree 1

[DotNetGnat]

Guys,

I have binary tree as follows

One Step
_________

A
/ \
B C

Two Steps
_________

A
/ \
B C
/ \ / \
D E E F

Three Steps
____________

A
/ \
B C
/ \ / \
D E E F
/ \ /\ /\ /\
G HH I H I I J

and so on...

I want to eliminate the duplicate nodes and result should like below:

One step
________
No Changes here

A
/ \
B C

Two Steps
___________

A
/ \
B C
/ \ / \
D E F

Three Steps
_____________

A
/ \
B C
/ \ / \
D E F
/ \ / \ / \
G H I J

I tried using InorderTraversal to relink the nodes but failed...any suggestions...

Thanks

-DNG

 

[jmeckley]

Looks like an Identity Map. the first thing you need is to override Equals and GetHashCode(). this will make it easier to compare objects. Then you will need to keep a reference to these items by type. there may already be a simple Id.Map. implementation out there.

Once you have the Id.Map. you can build the tree.

Jason Meckley
Programmer
Specialty Bakers, Inc.

faq855-7190
faq732-7259

 

[DotNetGnat]

never heard of an identity map...may be I should look into it...

also may be I need to build the binary tree that is free of duplicates to begin with...

thanks for your input...I appreciate it..

-DNG

 

[jmeckley]

yes, I would build the tree after the objects are loaded into the identity map. trying to remove duplicates from an existing tree will be a nightmare.

1. retrieve objects
2. load into identity map
3. build tree from objects in identity map.

Jason Meckley
Programmer
Specialty Bakers, Inc.

faq855-7190
faq732-7259

 

[DotNetGnat]

thank you Jason, thats exactly what I am going to do...

have a star...

-DNG