java - 如何在树 Java 中查找节点

Question

我是 Java 的初学者，我目前正在尝试解决树章节中的练习。

一棵树由这些节点组成。
enter image description here .一个节点保存一个对应于整数的值。
除了位于树根的节点之外，一个节点始终只有一个其他节点引用它。
如果一个节点在右边或左边没有子节点，那么对应的引用是 null .
左侧子树中任何子树的值都小于其父树的值，而右侧子树中任何子树的值都大于其父树的值。
树的高度在 0 到 100 000 节之间。

我正在尝试实现 find(int v)返回持有值 v 的节点的方法如果节点不存在，则 find 必须返回 null .

这是我一直在做的事情，但我有点迷茫:

class Node{
    Node left, right;
    int value;

    public Node find (int v){
        Node result = null;
        if (this.left != null) result = find(v);
        if (this.value == v) return this;
        if (result == null && this.right != null) 
            result = find(v);

        return result;     

    }

    public static void main (String[] args){
        Node n = smallNode.find(8);
        System.out.println(n);
        n = LargestNode.find(0);
        System.out.println(n);
    }
}

我收到了 StackoverOverflowError在这一行:

if (this.left != null) result = find(v);

我究竟做错了什么 ？我找不到它为什么会出现这个异常。

Answer 1

您应该先检查值，返回 this如果该节点具有您正在寻找的值。如果它不检查你可以从当前节点继续向右走，一旦你返回检查给定值的结果，如果正确返回该节点，否则返回左侧给出的任何内容。它将是具有您想要的值的节点或为空。

public Node find (int v){
    Node result = null;

    //check for value first
    if (this.value == v) return this;

    //check if you can go any further from the current node
    if(this.left == null && this.right == null) return null;

    //now go right
    result = this.right.find(v);

    //check the node
    if(result != null && result.value == v) return result;

    //if not found return whatever is returned by searching left
    return this.left.find(v);
}