如何获得泛型树中节点的级别？

Question

给定一个实现为根节点的泛型树，该根节点具有子节点列表，子节点是节点，并且每个节点都具有其子节点列表。

   __A__ 
  /  |  \
 B   C   D
 |  / \
 E  F  G 

节点a具有其子节点的列表:B、C、D

B、C、D也有他们儿子的名单:B-->E；C-->F、G；D-->空；

我将解释我的算法的想法，你可以修复它或给我另一个全新的想法。

public Integer level(T dato) {...}

遍历树，将树的每个节点添加到队列中，或者如果添加的最后一个节点是级别的最后一个节点，则添加一个“null”。Null是队列中的标识符，用于知道级别已结束的位置。我的问题是，我不知道第一次之后到底该把标识符放在哪里。下面是一些代码：

    public Integer level(T data){
    int inclu= this.include(data);
    if (inclu==-1) {        // if the tree doesn't include the data
        return -1;
    } else {               
        return inclu;       // returns the level
    }
}

public Integer include( T data ) {  // returns the level where the data is
    Integer inclu = -1;     // -1 if the data is not included
    if (this.getDataRoot()==data){
        return 0;       //  The root of the tree has the data
    }
    else {
        LinkedList<GenericNode<T>> queue = new LinkedList<GenericNode<T>>();

        GenericNode<T> tree = new GenericNode<T>();

        int level=1;
        queue.addAtBeginning(this.getRoot());
        queue.addAtBeginning(null);

        while (queue.size()>0 && inclu==-1) {

            if(queue.element(queue.size())!=null) {                         // if it is not the end of the level then dequeue

                tree.setData(queue.element(queue.size()).getData());        //queue.element(position) returns the element in that position
                tree.setListOfSons(queue.element(queue.size()).getSons());

                if (tree.getSons()!=null) {     // if the tree has sons
                    int i=1;
                    while(i<=tree.getSons().size() && inclu==-1) {
                        queue.addAtBeginning(tree.getSons().element(i));
                        if (tree.getSons().element(i).getData()==data)      // if I found the data I'm looking for
                            inclu=level;
                        i++;                                                // counter
                    }   
                }       
            } else {    // if it is the end of the level (means the queue gave me a null)
                level++;    
            }

            queue.delete(queue.size());         //ending the dequeue process

        } //end while
    } // end main else

    return inclu;       //returns the summation of the levels or 0 if it was found at the root of the tree or -1 if the data was not found
}

Answer 1

我写了一个类，它返回特定树中目标节点的级别。

import java.util.LinkedList;

import java.util.List;

public class TreeLevel {

public static class Node {
    public Node(String data) { this.data = data ; };
        public String data;
        public List<Node> childs = new LinkedList<Node>();
    }

public static Integer level(Node tree, Node target){
    return level(tree, target, 0);
}

private static Integer level(Node tree, Node target, int currentLevel) {
    Integer returnLevel = -1;        
    if(tree.data.equals(target.data)) {
        returnLevel = currentLevel;
    } else {
        for(Node child : tree.childs) {
            if((returnLevel = level(child, target, currentLevel + 1)) != -1){
                break;
            }                
        }
    }
    return returnLevel;

}

public static void main(String[] args) {

    Node a = new Node("A");
    Node b = new Node("B");        
    Node c = new Node("C");
    Node d = new Node("D");        
    Node e = new Node("E");
    Node f = new Node("F");
    Node g = new Node("G");

    // childs of a:
    a.childs.add(b);
    a.childs.add(c);
    a.childs.add(d);

    // childs of b:
    b.childs.add(e);

    // childs of c:
    c.childs.add(f);
    c.childs.add(g);

    // childs of d:
    // d.childs = null or simply d.childs.length() is 0 
    Node target = new Node("G");
    Integer level = level(a, target);
    System.out.println("level [" + level + "]");


  }
}