插入和查找节点结构

Question

我有点糊涂了，因为插入代码的代码是：

public Node insert(Node root, int data) {

    // if tree is empty, create it and return 
    if(root == null) 
        return root = new Node(data);

    // recursively insert new node
    if(data < root.data) 
        root.left = insert(root.left, data);

    else if(data > root.data)
        root.right = insert(root.right, data);

    return root;

}

找到一个节点是：

public Node find(Node root, int data) {

    if(root == null) 
        return null;

    if(root.data == data) {
        System.out.println(root.data + " found");
        return root;
    }


    if(data < root.data) 
        return find(root.left, data);
    else if(data > root.data)
        return find(root.right, data);

    return root;
}

你不能在查找方法中使用root.left = find(root.left, data)和root.right = find(root.right, data)而不是return find(root.left, data)和return find(root.right, data)吗？有什么不同？

Answer 1

在您建议的解决方案中，您正在为 root.left 和 root.right 赋值，这会改变树，这是您在 find 方法中绝对不想要的东西（应该离开树未受影响）。返回节点只是递归地寻找它，然后returns它。

主要区别是当你插入时，你确实想要改变树，即将新节点添加到适当的位置。当你想在树中找到一个节点时，你不想做任何赋值，只是return你要找的节点。

插入和查找节点结构

Inserting and Finding a Node Structure

java

binary-search-tree