Java实现树搜索

Question

我希望实现并测试一种树搜索功能。我正在使用javax.swing的DefaultTreeModel。我将自己定义的Employee对象作为树数据进行操作。我尝试使以下内容正常工作：

    private DefaultMutableTreeNode search(int id, DefaultMutableTreeNode node){
    if(node != null){
        Employee emp = (Employee) node.getUserObject();
        if(emp.getId() == id){
           return node;
        } else {
            DefaultMutableTreeNode foundNode = search(id, node.getPreviousSibling());
            if(foundNode == null) {
                foundNode = search(id, node.getNextSibling());
            }

            return foundNode;
         }
    } else {
        return null;
    }
}

但它只能在一个父元素的同级元素中查找元素。如果想要在整个树中从根节点到叶子节点查找元素，应该怎么做呢？

- Michał Szydłowski

Answer 1

你可以先使用另一种方法导航到树的根，然后调用当前的递归方法。

private DefaultMutableTreeNode search(int id, DefaultMutableTreeNode node){
    if(node == null){
        return null;
    }
    node = node.getRoot(); //Turns out that this class has a getRoot() method.
    return searchInternal(id,node); //Then does a depth-first search from the root node.
}

private DefaultMutableTreeNode searchInternal(int id, DefaultMutableTreeNode node){
    if(node == null){ //I also switched this around, for good practice.
        return null;
    }
    Employee emp = (Employee) node.getUserObject();
    if(emp.getId() == id){ //Found it!
        return node;
    }
    DefaultMutableTreeNode foundNode = searchInternal(id, node.getPreviousSibling());
    if(foundNode == null) {
        foundNode = search(id, node.getNextSibling());
    }

    return foundNode;
}

通常情况下，在Java中，递归方法往往运行速度较慢，并且容易出现堆栈溢出的问题。使用自定义堆栈进行深度优先搜索通常更好，这不需要您编写不同的方法。在某些情况下，递归方法可能会使代码更易读。

在这种情况下，还有其他可行的方法：

private DefaultMutableTreeNode search(int id, DefaultMutableTreeNode node){
    if(node == null){
        return null;
    }
    Enumeration enumeration = node.getRoot().depthFirstEnumeration(); //Enumerate over all nodes in the tree.
    while(enumeration.hasMoreElements()){
        DefaultMutableTreeNode next = enumeration.next();
        if(((Employee)next.getUserObject()).getId() == id){ //Found it!
            return next;
        }
    }
    return null;
}

原来 Swing 已经实现了深度优先搜索，不过这是后序遍历。请参阅 javadoc，其中还有其他类型遍历的方法。

- Ghostkeeper