Searching for a certain binary tree from another tree........
I have been struggling for a tree search problem for a good while. Now I decide to ask you experts for a better solution :-).
Given a binary tree A. We know that every Node of A has two pointers. Leaves of A can be tested by if(node.right = =node). Namely, The right pointer of every leaf node points to itself. (The left pointer points to the node sits on the left side of the leaf in the same depth. and the leafmost node points to the root. I do no think this information is important, am i right?).
Tree B has a similar structure.
The node used for both A and B.
Node{
Node left;
Node right;
}
My question is how to test if tree B is a subtree of A and if it is, returns the node in A that corresponds to the root of B. otherwise, return null.
So, the method should look like:
public Node search(Node rootOfA, Node rootOfB){
........
}
I know a simple recursive fuction can do the job. The question is all about the effciency....
I am wonderring if this is some kind of well-researched problem and if there has been a classical solution.
Anyone knows of that? Any friend can give a sound solution?
Thank you all in advance.
Jason
Message was edited by:
since81
[1287 byte] By [
since81a] at [2007-10-2 23:56:47]
I'm not too sure if this would help but there goes.
I think a recursive function will be the easiest to implement (but not the most efficient). In terms of recursive function if you really want to add performance. You could implement your own stack and replace the recursive function with the use of this stack (since really the benefit of recursive function is that it manages its own stack). A non-recursive function with customized well implemented stack will be much more efficient but your code will become more ugly too (due to so many things to keep track of).
Is tree B a separate instance of the binary tree? If yes then how can Tree B be a subset/subtree of tree A (since they are two separate "trees" or instances of the binary tree). If you wish to compare the data /object reference of Tree B's root node to that of Tree A's then the above method would be the most efficient according to my knowledge. You might have to use a Queue but I doubt it. Stack should be able to replace your recursive function to a better more efficient subroutine but you will have to manage using your own stack (as mentioned above). Your stack will behave similar to the recursive stack to keep track of the child/descendant/parent/root node and any other references that you may use otherwise.
:)
Thanks for the reply,,spungebob.
I really do not want to matain my owen stack.
For you question
"Is tree B a separate instance of the binary tree? If yes then how can Tree B be a subset/subtree of tree A (since they are two separate "trees" or instances of the binary tree)"
Tree B is a separate instance of A. All the nodes in A has nothing to do with B and vice versa. Only the shape matters. So, when I am saying search for B from A, I actually mean search if tree A has a subtree that is of the same shape of B.
I have impemented this search algo using a exaustive recursion.
Indeed, it runs really slow. :-(
> I have impemented this search algo using a exaustive
> recursion.
Good, you figured it out.
> Indeed, it runs really slow. :-(
How slow? How did you test it? What does your algorithm look like?
Maybe you can post the code here so that other can point out errors in it.
That's a kind offer, mate.
As I have tested my code over a fairly large test suite. I am sort of confident at the correctness...
As the tree I am using is in fact not a Binary tree. It is called the PPCT tree. and the search function does a lot of other stuff at the same time traversing the tree( like storing a list of nodes that can be used as boundary to discribe the position of treeB inside TreeA.)
It is going to take me a while to explain the whole idea and i am really not very good at english. :-(
I will do it once I get some more free time.
Thanks for the help!
Here's my recursive solution, just for the fun of it; it assumes two ordinary
binary trees (leafs have both null left/right sub-trees). Just two little
methods do the job:private boolean equals(Node a, Node b) { // check if a has same structure as b
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return equals(a.left, b.left) && equals(a.right, b.right);
}
public Node search(Node a, Node b) { // check if b in a
if (equals(a, b)) return a;
Node sub;
if (a != null) {
if ((sub= search(a.left, b)) != null) return sub;
return search(a.right, b);
}
return null;
}
kind regards,
Jos
JosAHa at 2007-7-14 16:43:30 >
All you are asking is if B is a child of A.
Even if B is one node or null it is still a tree.
You wouldnt need to return the node in A that corrosponds to the root of B because you already have B.
Do a binary search on A for B.
It can return boolean since you already have B.
