关于菜单树排序问题的解决方案（一）

最近在做菜单管理的展示时，发现树形列表必须按照父在子前且子紧随父才能正确的展示，经过查阅资料后找到两种解决方案，一种是使用递归进行排序，另一种是使用多叉树进行遍历，使用多叉树进行遍历的方案请参考《关于菜单树排序问题的解决方案（二）》。我对这两种方案都简单封装了下，本文作为备忘。

使用递归对菜单树进行排序

1. 树节点的接口

public interface TreeNode<S>{
    S getId();
    S getPId();
    /**
     * 怎样判断节点是不是根节点
     */
    boolean isRootNode();
}

2. 递归排序

/**
 * 递归方式对list树遍历
 * T 节点类型
 * K 节点id和pId的类型
 */
public class TreeListSort<T extends TreeNode,K> {
    List<T> nodes;
    List<T> resultList;

    /**
     * 获取排序后的list
     */
    public List<T> getSortTreeList(List<T> nodeList){
        nodes=nodeList;
        resultList=new ArrayList<>();
        for (T node:nodes){
            if (node.isRootNode()){
                resultList.add(node);
                if (hasChild((K) node.getId())){
                    traverseChildren((K) node.getId());
                }
            }
        }
        return resultList;
    }

    /**
     * 遍历子节点
     */
    public void traverseChildren(K id){
        for (T node:nodes){
            if (node.getPId()!=null&&node.getPId().equals(id)){
                resultList.add(node);
                if (hasChild((K) node.getId())){
                    traverseChildren((K) node.getId());
                }
            }
        }
    }

    /**
     * 判断是否有子节点
     */
    public boolean hasChild(K id){
        for (T node:nodes){
            if (node.getPId()!=null&&node.getPId().equals(id)){
                return true;
            }
        }
        return false;
    }
}

3. 具体节点的实体

/**
 * 继承树节点接口并实现获取id、父id以及判断是否是根节点的方法
 */
public class TestNode implements TreeNode<Integer> {
    private int nodeId;
    private String nodeName;
    private int nodePId;
    @Override
    public Integer getId() {
        return nodeId;
    }
   @Override
    public Integer getPId() {
        return nodePId;
    }
   @Override
    public boolean isRootNode() {
        return nodePId == 0;
    }
    public TestNode() {
    }
    public TestNode(int nodeId, String nodeName, int nodePId) {
        this.nodeId = nodeId;
        this.nodeName = nodeName;
        this.nodePId = nodePId;
    }
}

4. 使用

public class Main {
    public static void main(String []args){
        List<TestNode> testNodes=new ArrayList<>();
        testNodes.add(new TestNode(1,"1",0));
        testNodes.add(new TestNode(2,"2",0));
        testNodes.add(new TestNode(3,"3",0));
        testNodes.add(new TestNode(4,"1-4",1));
        testNodes.add(new TestNode(5,"2-5",2));
        testNodes.add(new TestNode(6,"3-6",3));
        testNodes.add(new TestNode(7,"1-4-7",4));
        testNodes.add(new TestNode(8,"1-4-8",4));
        testNodes.add(new TestNode(9,"2-5-9",5));
        testNodes.add(new TestNode(10,"2-5-9-10",9));
        testNodes.add(new TestNode(11,"2-5-9-10-11",10));
        testNodes.add(new TestNode(12,"2-5-9-10-11-12",11));
        testNodes.add(new TestNode(13,"2-5-9-10-11-12-13",12));
        testNodes.add(new TestNode(14,"2-5-9-10-11-12-13-14",13));
        testNodes.add(new TestNode(15,"2-5-9-10-11-12-13-14-15",14));
        //使用递归进行遍历
        TreeListSort<TestNode,Integer> treeSort=new TreeListSort<>();
        List<TestNode> list=treeSort.getSortTreeList(testNodes);
        for (TestNode node:list){
            System.out.println(node.toString());
        }
    }
}

使用多叉树进行遍历：《关于菜单树排序问题的解决方案（二）》
如有错误或者不足请指正，谢谢！