时间戳

首页 > 解决方案 > 二叉搜索树不会添加新节点？

java - 二叉搜索树不会添加新节点？

问题描述

我正在尝试编写一种递归方法来将节点添加到二叉搜索树（不允许重复）。由于某种原因，该方法仅在树为空时有效，否则它会打印出“重复”（即使它不是重复的）。我是编程新手，希望能得到解决此问题的帮助和提示。谢谢你。

//add new node to the tree
public void add(int data) {
    Node<Integer> newNode = new Node<>(data); //create new node with the data

    //if the tree is empty, the newNode becomes the root
    if (size() == 0) {
        root = newNode;
        return;
    }
    //otherwise, check if node should be placed to right or left 
    add(data, root);
}
private void add(int data, Node<Integer> node) {
    //base case - found an empty position
    if (node == null) {
        node = new Node<Integer>(data);
    }
    if (data < node.data) {
        add(data, node.left);
    }
    else if (data > node.data) {
        add(data, node.right);
    }
    else if (data == node.data) {
        System.out.println("Duplicate. This value cannot be added to the tree.");
    }
}

标签： javatreebinary-treebinary-search-treebinary-search

解决方案

当您的树为空时，节点会正确添加到其中。第一个add(int data)功能很好。

第二个add(int data, Node<Integer> node)功能存在问题。如果树已经有一个元素，则调用此方法。如果传递的节点大于或小于传递的值，则使用当前节点的左子或右子再次调用该函数。这个值可能（最终会）为空。这导致在您的方法的基本情况下创建一个节点，从而满足此data == node.data条件，因为该节点确实是使用数据值创建的。因此，您会收到错误消息。

为了解决这个问题，第二个功能可以改变如下：

private void add(int data, Node<Integer> node) {
    if (data < node.data) {
        if (node.left != null) {
            add(data, node.left);
        } else {
            node.left = new Node<>(data);
        }
    }
    else if (data > node.data) {
        if (node.right != null) {
            add(data, node.right);
        } else {
            node.right = new Node<>(data);
        }
        add(data, node.right);
    }
    else if (data == node.data) {
        System.out.println("Duplicate. This value cannot be added to the tree.");
    }
}

看到基本案例已被移除。如果遇到基本情况，我们不会为我们提供对任何树节点的引用。因此添加data到树是不可能的（节点参数绝不能为空）。

此外，如果子项为空，代码将添加data为子项。node这保证了该方法不会递归地使用 nullnode参数，并且data更重要的是添加到其应有的位置。

推荐阅读