5 Replies - 365 Views - Last Post: 09 January 2013 - 05:43 PM Rate Topic: -----

#1 aya_eltokhy  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 07-November 12

tree equivalence

Posted 09 January 2013 - 03:00 PM

hi :001_icon16: :001_icon16:
i have this code which determined if tow trees are equal or not
the code is working in these cases:
1: equals;
8 8
4 20 4 20

2: the roots not equals
8 80
4 20 4 20

and does not worked in this case
8 8
40 20 4 200



what is the error
 int  bt_equal  (  binarytree  * tree1,   binarytree * tree2)
{    int   res;
     if  (  tree1 == NULL &&  tree2 == NULL )
               return (  True  ) ;
    res = False ;
    if (  tree1  ->   data ==  tree2  ->   data  )
      {  res = bt_equal  (  tree1->   lchild  ,  tree2  ->   lchild ) ;
              if  ( res  == True )
                res = bt_equal  (  tree1  ->   rchild  ,  tree2  ->   rchild ) ;
        }
            return  ( res );
}



case one:
tree 1
8 root
4 lchild
20 rchild


tree2
8 root
4 lchild
20 rchild

case 2
tree 1
8 root
4 lchild
20 rchild


tree2
80 root
4 lchild
20 rchild


case 3
tree 1
8 root
40 lchild
20 rchild


tree2
8 root
4 lchild
200 rchild

Is This A Good Question/Topic? 0
  • +

Replies To: tree equivalence

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3463
  • View blog
  • Posts: 10,669
  • Joined: 05-May 12

Re: tree equivalence

Posted 09 January 2013 - 03:52 PM

I must be missing it, but the code as posted should correctly return False for case 3:
            data lchild  rchild
tree1  -> { 8,   child1, child2 }
child1 -> { 40,  NULL,   NULL }
child2 -> { 20,  NULL,   NULL }
tree2  -> { 8,   child3, child4 }
child3 -> { 4,   NULL,   NULL }
child4 -> { 200, NULL,   NULL }

result = bt_equal(tree1, tree2)
         res = False
         if (8 == 8)
            res = bt_equal(child1, child3)
                  res = False
                  if (40 != 4)
                      // skip
                  return False
            res = False
         return False
result = False


Was This Post Helpful? 1
  • +
  • -

#3 aya_eltokhy  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 07-November 12

Re: tree equivalence

Posted 09 January 2013 - 04:11 PM

thanks for helping :flowers:

do you have class for tree has all function???
Was This Post Helpful? 0
  • +
  • -

#4 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: tree equivalence

Posted 09 January 2013 - 04:20 PM

I also don't see why case 3 is returning the wrong result, but I do see an issue with the code if you are passed two trees with different shapes. For example, your code will crash if we pass a tree with only a left child and a tree with only a right child. You need to add cases for when one of the input nodes is null and the other is not.
Was This Post Helpful? 1
  • +
  • -

#5 aya_eltokhy  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 19
  • Joined: 07-November 12

Re: tree equivalence

Posted 09 January 2013 - 04:33 PM

i think the problem in the insertion part
void insert(int key)
	{ binarytree *p,*q;
	  if (root==NULL)
	  {
		  root=new binarytree;
		  cout<<root<<"\n";
		root->data=key;
		root->lchild=NULL;
		cout<<"\n"<<root->lchild;
		root->rchild=NULL;
		cout<<"\n"<<root->rchild;
		return;
	  }

	  else{
	  p=root;
	  while(p!=NULL)
	  {
	     q=p;
		 if(key>p->data)
			 p=p->rchild;
		 else
			 p=p->lchild;

	  }

	  p=new binarytree;
	  p->lchild=NULL;
	  p->rchild=NULL;
	  p->data=key;
	  if(key>q->data)
	  { q->rchild=p;
	     cout<<"\n"<<q->lchild;
	  }
	  else
	  {q->lchild=p;
	   cout<<"\n"<<q->rchild;
	  }
	  }

	}


Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3463
  • View blog
  • Posts: 10,669
  • Joined: 05-May 12

Re: tree equivalence

Posted 09 January 2013 - 05:43 PM

I don't see what the cout's are buying you in your insert() function unless you are also running your code in a debugger and keeping an eye on the pointer values.

BTW, your cout's for left and right child pointers seem to be swapped on lines 33 and 37.

Also, your current insert() will fail to reproduce tree1 in case 3, because tree1 in case 3 has left child greater than the root which breaks your tree rule here left child must be less than the root.

This post has been edited by Skydiver: 09 January 2013 - 05:44 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1