Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By jim829

Thread: Searching through Trees

  1. #1
    vx117 is offline Member
    Join Date
    Dec 2012
    Posts
    22
    Rep Power
    0

    Default Searching through Trees

    I'm trying to write a code that only searches through the immediate children of a tree.

    This is what I have:
    Java Code:
    /**
         * findChild: searches through the *immediate* children of the tree
         * to see if there is a subtree N whose label is equal to {@link otherLabel}.
         */
        public Tree<T> findChild(T otherLabel) {
        	while (parent != null && firstChild != null ){
        			if (firstChild == otherLabel){
        				break;
        			}
        			else {
        				firstChild = nextSibling;	
        			}	  
        	}
        	return firstChild;
        }
    Can anyone check if it is correct and is iterating through the nodes correctly? Thanks.

    If my directions are not clear, here are the original directions :

    Your first task is to implement a member method of the Tree<T> class. In particular you will implement findChild(T lab) which searches through the immediate children of the tree, and if it finds a child subtree S such that Sís label is equal() to lab, it returns S. It returns null if no such subtree is found. For example, letís say we have a tree called myTree<String> whose label is ďaĒ and has child subtrees as follows:

  2. #2
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,767
    Rep Power
    5

    Default Re: Searching through Trees

    Based on your description you should use equals and not == for equality checks. And the equals method and hashCode should be overridden in accordance with the equals contract. For some JDK classes like String, this is already done. But homegrown classes it is essential. Otherwise, your just comparing references.

    Also, otherLabel is of type T. But there is no indication of how you have defined firstChild or nextSibling. Are these labels or simply classes that have labels
    as instance fields?

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    vx117 is offline Member
    Join Date
    Dec 2012
    Posts
    22
    Rep Power
    0

    Default Re: Searching through Trees

    Thanks for the reply. Here is the rest of my code for a better understading.

    Java Code:
     private T label;
        private Tree<T> parent;
        /** 
         * next node on the list of parent's children
         */
        private Tree<T> nextSibling; 
        /**
         * first in the linked list of children
         */
        private Tree<T> firstChild;
    
        public Tree(T l) {
    	label = l; parent = null; nextSibling = null; firstChild = null; 
        }
        public Tree() {
    	label = null; parent = null; nextSibling = null; firstChild = null; 
        }
                                     
        /**
         * getters and setters
         */
        public T getLabel() { return label; }  
        public void setLabel(T v) { label = v; }
        public Tree<T> getParent() { return parent;}
        public Tree<T> getNextSibling() { return nextSibling;}
        public Tree<T> getFirstChild() { return firstChild;}

  4. #4
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,767
    Rep Power
    5

    Default Re: Searching through Trees

    I assume that is the Tree<T> class. The problem is that in your first snippet of code you are comparing instances of Tree<T> to some instance of T which doesn't make sense. For each instance of Tree<T> tree you need to compare tree.getLabel() to otherLabel. And I would recommend changing firstChild to currentChild, since it is changing as you iterate thru the tree.

    Regards,
    Jim
    vx117 likes this.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Similar Threads

  1. swing trees
    By willemjav in forum AWT / Swing
    Replies: 7
    Last Post: 10-06-2013, 06:56 PM
  2. Help with binary trees please
    By sim18 in forum New To Java
    Replies: 3
    Last Post: 11-27-2012, 07:34 PM
  3. Visuallizing Trees
    By mike_ledis in forum Advanced Java
    Replies: 2
    Last Post: 01-17-2012, 09:24 PM
  4. Game Trees
    By javaBoy1 in forum Advanced Java
    Replies: 0
    Last Post: 12-27-2008, 12:20 AM
  5. Help With Tournament Trees
    By wiggsfly in forum New To Java
    Replies: 2
    Last Post: 10-26-2008, 09:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •