Recursive search to delete n'th child in tree

Question

I have to implement a tree programming here. What I mean by tree programming is I have data stored in tree format. I have a parent object which will have child objects of same type the level of depth can go any long:

I am able to store objects in tree format and also able to display properly. I am facing problems when I have to filter some child nodes based on some conditions:

I have two question:

is this code fine?
is there anything wrong with design?

Plus, how can I handle removing child node in a tree where the child can be in any place?

package menu;
import java.util.List;
public class Links{
private String nodeName;
     private List<Links> children;

     public List<Links> getChildren(){
        return children;
     }

     public void setChildren( List<Links> children ){
        this.children = children;
     }

     public String getNodeName(){
        return nodeName;
     }

     public void setNodeName( String nodeName ){
        this.nodeName = nodeName;
     }
}




  package menu;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.chartis.gp.support.util.BrokerSupportUtil;
import com.chartis.gp.support.vo.Links;
import com.chartis.kernel.user.UserVO;
import com.chartis.kernel.utils.Utils;

public class Utility{

    /* IN this class NavModel,CModel,CNode are some dummy classes
     * which help us read contents form some resources which are stored in dummy format
     * as Example of tree format stored data below is the example 
     *    tree
     *       child1
     *       child2
     *       child3 
     *              child3-1
     *                       child:q
     *                       child:r
     *                               child:a
     *              child3-2
     *              
     *       child4 
    */


    private static void populateChildLinks(NavModel navModel, Object objectNode, Links parent ){
        try{
            List<Links> childLinks = new ArrayList<Links>();
            Iterator it = navModel.getChildren( objectNode );
            while( it.hasNext() ){
                NavNode node = (NavNode) it.next();
                CNode contentNode = node.getContentNode();

                Links links = new Links();

                links.setNodeName( contentNode.getNodeName() );

                childLinks.add( links );

                if( navModel.hasChildren( node ) ){
                    populateChildLinks( node, links );
                }
            }
            parent.setChildren( childLinks );

        }
        catch( Exception e ){

        }

    }

    private static Links createCategoryLinks(String categoryLinkName){
        Links categoryLinks = new Links();
        categoryLinks.setNodeName( categoryLinkName );
        return categoryLinks;
    }

    public static Links setupLinks(String categoryLinkName,String name) {
        Links categoryLinks=null;
        CModel contentModel = new CModel();
        NavModel navModel = new NavModel();
        categoryLinks = Utility.createCategoryLinks( categoryLinkName);
        Object objectNode = contentModel.getLocator().findByUniqueName(name);
        if( objectNode != null ){
            if( navModel.hasChildren( objectNode ) ){
                populateChildLinks( navModel,objectNode, categoryLinks );
            }
        }
    }

              // This is where i am facing issue once i get list of links of childs 
        // i have to delete how can i find that particular child in the list
        // do i have to iterate through all the links and delete or  which 
        // way is better
    private static void filterLinks( Links parentNode,
            List<Links> childNodeList ){
        List<Links> filteredResourceList = new ArrayList<Links>();
        if(  childNodeList!=null ){
            Iterator<Links> childNodeIt = childNodeList.iterator();
            while( childNodeIt.hasNext() ){
                Links childNode = (Links) childNodeIt.next();
                if(childNode.getChildren().size() >0 ){
                    filterLinks( childNode, childNode.getChildren() );
                }

                boolean removeNode = filterContents( childNode);
                if(! removeNode ){
                    filteredResourceList.add( childNode );
                }

            }
        }
        Iterator<Links> filteredResourceIt = filteredResourceList.iterator();
        while( filteredResourceIt.hasNext() ){
            Links childNode = (Links) filteredResourceIt.next();
            parentNode.getChildren().remove( childNode );
        }
    }

    // Let us consider this as some dummy method which returns true or false based on some conditions
    private static boolean filterContents( menu.Links childNode ){

        return false;
    }
}


package menu;

public class TreeDisplay{
    public static void main( String[] args ){
        Links link = Utility.setupLinks( "SomeName", "ResiyrbceBane" );
        Utility.filterLinks( link, link.getChildren() );
    }
}

Once I have a list of objects, I have to delete since it is tree object. How canI delete a child? I know I have to do a recursive search, but how can I do that? Which way will I delete? In the above tree structure where I have commented in the code, how can I delete child:q?

seand · Accepted Answer · 2012-12-18 13:36:14Z

It is not possible to test your classes, because of:

import com.chartis.gp.support.util.BrokerSupportUtil;
import com.chartis.gp.support.vo.Links;
import com.chartis.kernel.user.UserVO;
import com.chartis.kernel.utils.Utils;

But ok, the general idea is ( if we want to use recursion):

remove(child, tree):
    if tree.isLeaf: return false
    if tree.hasChild(child): tree.removeChild(child); return true;
    for all children of tree as subtree:
        if remove(child, subtree): return true;
    return false;

Methods you will most probably need:

public void addChild(Links child)
{
    children.add(child);
}

public boolean hasChild(Links child)
{
    return children.contains(child);
}

public boolean removeChild(Links child)
{
    return children.remove(child);
}

public boolean isLeaf()
{
    return children.size() <= 0;
}

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((nodeName == null) ? 0 : nodeName.hashCode());
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Links other = (Links) obj;
    if (nodeName == null) {
        if (other.nodeName != null)
            return false;
    }
    else if (!nodeName.equals(other.nodeName)) //hint: this only works if nodeName is unique! If not, use a unique static counter
        return false;
    return true;
}

Take a look at some of the tree-classes of java to see some typical methods.

And your method could look like:

public static boolean removeChildFromTree(Links child, Links tree)
{
    if (tree.isLeaf()) //we are at a leave, we can not delete any children anymore
        return false;
    if (tree.hasChild(child)) //we found it, quickly delete it
        return tree.removeChild(child);
    //we have to search all children
    for (Links subTree : tree.getChildren())
    {
        if (removeChildFromTree(child, subTree)) //try to delete on subtree
            return true;
    }
    return false;
}

Edit: Just to point out, this code is not for efficiency. It is written for clarity. Do not care about efficiency before you really have to.

Thank you for the ans-were can you kindly let me know why do we have to override equals and hashcode mehtods — VIckyb
– VIckyb, Commented Dec 11, 2012 at 5:34
You need to override equals, if two different trees with the same content should be considered equal (the default implementation tests only for reference equality). For hashCode, see the remarks in the API doc: docs.oracle.com/javase/7/docs/api/java/lang/… — Landei
– Landei, Commented Dec 11, 2012 at 9:05
Just a small addition to the comment from @Landei. The method hasChild calls the contains method from List. As one can expect, to know if something is inside a list, each element must be checked if it is equal to the given element. The contract is specified in the Java API: docs.oracle.com/javase/7/docs/api/java/util/… — tb-
– tb-, Commented Dec 11, 2012 at 13:01

Stack Exchange Network

Recursive search to delete n'th child in tree

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Recursive search to delete n'th child in tree

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions