java - 如何搜索具有三个子节点的树？

Question

我的树节点有 3 个字符串字段和 3 个节点字段，即左、中、右。

问题之一是该方法只能接受字符串作为参数

这就是我所拥有的

public TreeNode findNode(String name) {
    TreeNode pointer = this.getRoot();

    if (pointer.getName().equals(name))
        return pointer;
    if (pointer.getLeft() != null)
        pointer = pointer.getLeft();
    findNode(name);
    if (pointer.getMiddle() != null)
        pointer = pointer.getMiddle();
    findNode(name);
    if (pointer.getRight() != null)
        pointer = pointer.getRight();
    findNode(name);
    return null;

}

这会导致堆栈溢出错误，因为我只是不断将指针设置为根。但我必须从某个地方开始，并且该方法的唯一参数可以是名称。我似乎不知道该怎么做。

Answer 1

您可以使用列表作为参数堆栈。

public TreeNode findNode(String name) {
    List<TreeNode> stack = new ArrayList<TreeNode>();
    stack.add(this.getRoot());
    while (!stack.isEmpty())
    {
        TreeNode node = stack.remove(0);
        if (node.getName().equals(name))
            return node;
        if (pointer.getLeft() != null)
            stack.add(node.getLeft());
        if (node.getMiddle() != null)
            stack.add(node.getMiddle());
        if (node.getRight() != null)
            stack.add(node.getRight());
    }
    return null;
}

如果您想深度优先搜索，可以从列表末尾而不是列表前面删除。