

 Thread Tools  Search this Thread 
#1
 
 
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. 
#2
 
 
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); } 
#3
 
 
Re: Test the equivalence of two binary trees In fact I have an expression such as E1 = (A+B)*(C+D)/(CD) 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. 
#4
 
 
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"? 
#5
 
 
Re: Test the equivalence of two binary trees For E1 = (A+B)*(C+D)/(CD), for example, was this (sorry for the layout, this thing is capricious): Code: (*) / \ () (/) / / \ (+) (+) (+) / \ / \ / \ A B C D C D 
#6
 
 
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. 

Tags: binary tree, java, java tree 
Thread Tools  Search this Thread 

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  27082011 07:45 AM 
What are Giant Trees in FarmVille  Lipika  Video Games  5  20022011 05:32 AM 
Ornamental Trees in FarmVille  Lizbeth  Video Games  5  11022011 06:54 AM 
How to use Trees in Java?   Empty Shell   Software Development  4  12022010 01:36 AM 
DNS test fails with dcdiag /test:dns  TEST: Forwarders/Root hints (Forw)  MartinH  Windows Server Help  6  20062006 07:20 PM 