Go Back   TechArena Community > Software > Software Development
Become a Member!
Forgot your username/password?
Tags Active Topics RSS Search Mark Forums Read

Reply
 
Thread Tools Search this Thread
  #1  
Old 05-11-2009
Member
 
Join Date: May 2009
Posts: 640
Test the equivalence of two binary trees

I want to make a java code which tests the equivalence of two binary trees. For trivial cases (tree size 0,1, ...) the code seems pretty obvious. However when the size is increasing, I can not determine an algorithm that returns me the correct results. Could you help me find this algo so that I can continue to code? Or give me links? On google I did not really find what I want by searching this algo.
Reply With Quote
  #2  
Old 05-11-2009
Member
 
Join Date: May 2008
Posts: 685
Re: Test the equivalence of two binary trees

When you say equity, you mean full equality, the 2 trees and structurally identical data? If so this should be a recursive algorithm in this style:

Code:
boolean estEgal(Node node1, Node node2) {
     if(node1 == null) 
     {
          return (node2 == null);
     }
     if(node2 == null) 
     {
          return false;
     }
     return (node1.value == node2.value) && isEqual(node1.childLeft, node2.childLeft) && isEqual(node1.childRight, node2.childRight);
}
And you call him from the root node of the two trees to compare.
Reply With Quote
  #3  
Old 05-11-2009
Member
 
Join Date: May 2009
Posts: 640
Re: Test the equivalence of two binary trees

In fact I have an expression such as

E1 = -(A+B)*(C+D)/(C-D)
E2 = (A*C + A*D + B*C + B*D) / (D ? C)

I have to build two trees with and create a method that determines if two trees are equivalent. For example A1.isEqual(Tree A2) should return true in this case.
Reply With Quote
  #4  
Old 05-11-2009
Member
 
Join Date: May 2008
Posts: 685
Re: Test the equivalence of two binary trees

OK but it does not answer my questions:

1) How does your binary tree represents these formulas? What is their in the leaves?
2) What is the definition of "equivalent"?
Reply With Quote
  #5  
Old 05-11-2009
Member
 
Join Date: May 2009
Posts: 640
Re: Test the equivalence of two binary trees

For E1 = -(A+B)*(C+D)/(C-D), for example, was this (sorry for the layout, this thing is capricious):

Code:
                (*)
               /     \
           (-)        (/)
          /          /   \
       (+)        (+)   (+)
      /    \      /  \   /  \
     A     B    C     D C    D
And just for the definition! Nothing in my course! Not to mention google
Reply With Quote
  #6  
Old 05-11-2009
Member
 
Join Date: May 2008
Posts: 685
Re: Test the equivalence of two binary trees

So nodes contain operations and leaves contain constants. Already, it allows multiple representations of the same formula. In fact this representation form of binary tree is more suitable for RPN(Reverse Polish Notation).

For me two binary trees are equivalent to two trees that contain exactly the same elements, but that does not respond to your statement (refer to the true representation of E1 and E2) ... you should ask for more information.
Reply With Quote
Reply

  TechArena Community > Software > Software Development
Tags: , ,



Thread Tools Search this Thread
Search this Thread:

Advanced Search


Similar Threads for: "Test the equivalence of two binary trees"
Thread Thread Starter Forum Replies Last Post
Seagate Device ST3250410AS Failed Long Test but passed Short Test Bryant Hardware Peripherals 5 27-08-2011 07:45 AM
What are Giant Trees in FarmVille Lipika Video Games 5 20-02-2011 05:32 AM
Ornamental Trees in FarmVille Lizbeth Video Games 5 11-02-2011 06:54 AM
How to use Trees in Java? - Empty Shell - Software Development 4 12-02-2010 01:36 AM
DNS test fails with dcdiag /test:dns - TEST: Forwarders/Root hints (Forw) MartinH Windows Server Help 6 20-06-2006 07:20 PM


All times are GMT +5.5. The time now is 06:05 PM.