java通用BST未插入所有值并返回null

Question

我正在尝试实现一个通用的二进制搜索树。我插入了7个整数，希望它们以顺序遍历的方式返回，但是它只返回4个无序的值。然后我检查树是否包含特定的值，但它总是返回null，我不确定为什么。我将在下面发布代码，你知道为什么我的输出是这样吗？我知道我的问题可能在我的insert和find方法中，但不确定为什么，最好做一些澄清。谢谢你的建议，谢谢

插入整数15、10、20、5、13、11、19时的输出：

run:
InOrder: 
Inorder traversal:  10 15 11 19 
Is 11 in the tree? null
BUILD SUCCESSFUL (total time: 0 seconds)

节点。类别：

class Node<E> {
  protected E element;
  protected Node<E> left;
  protected Node<E> right;

  public Node(E e) {
    element = e;
  }
}

二元搜索树。类别：

class BinarySearchTree<E extends Comparable<E>> {
  private Node<E> root;

  public BinarySearchTree() {
    root = null;
  }

  public Node find(E e) {
    Node<E> current = root;

    while (e.compareTo(current.element) != 0) {
      if (e.compareTo(current.element) < 0) {
          current = current.left;
      }
      else {
          current = current.right;
      }
      if (current == null) {
          return null;
      }
    }
    return current;
  }

  public void insert(E e) {
    Node<E> newNode = new Node<>(e);

    if (root == null) {
        root = newNode;
    } else {
        Node<E> current = root;
        Node<E> parent = null;

        while (true) {
            parent = current;
            if (e.compareTo(current.element) < 0) {
                current = current.left;
            }
            if (current == null) {
                parent.left = newNode;
                return;
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }
  }

  public void traverse(int traverseType) {
    switch(traverseType) {
      case 1: System.out.print("\nPreorder traversal: ");
          preOrder(root);
          break;
      case 2: System.out.print("\nInorder traversal:  ");
          inOrder(root);
          break;
      case 3: System.out.print("\nPostorder traversal: ");
          postOrder(root);
          break;
    }
    System.out.println();
  }

  private void inOrder(Node<E> localRoot) {
    if (localRoot != null) {
      inOrder(localRoot.left);
      System.out.print(localRoot.element + " ");
      inOrder(localRoot.right);
    }
  }

  private void preOrder(Node<E> localRoot) {
    if (localRoot != null) {
      System.out.print(localRoot.element + " ");
      preOrder(localRoot.left);
      preOrder(localRoot.right);
    }
  }

  private void postOrder(Node<E> localRoot) {
    if (localRoot != null) {
      postOrder(localRoot.left);
      postOrder(localRoot.right);
      System.out.print(localRoot.element + " ");
    }
  }

}

主要类别：

public class BST_Test{
  public static void main(String[] args) {
    testInteger();
  }

  static void testInteger() {
    BinarySearchTree<Integer> itree = new BinarySearchTree<>();
    itree.insert(15);
    itree.insert(10);
    itree.insert(20);
    itree.insert(5);
    itree.insert(13);
    itree.insert(11);
    itree.insert(19);

    // Traverse tree
    System.out.print("InOrder: ");
    itree.traverse(2);

    // Search for an element
    System.out.println("Is 11 in the tree? " + itree.find(11));
  }
}

Answer 1

原因是你的格式不好的代码隐藏了insert方法不正确的事实

这个if语句没有开头的大括号{（以及随后的结尾大括号}，因为它编译了），因此只有后面的语句包含在这个if块中：

if (e.compareTo(current.element) < 0)
    current = current.left

这意味着无论上述条件是否为真，都将执行以下操作

if (current == null) {
    parent.left = newNode;
    return;
} ...

。。。因此，如果current != null，您的插入将继续向右：

... else {
    current = current.right;
    if (current == null) {
        parent.right = newNode;
        return;
    }
}

---

当格式化/缩进适当时，完整的当前错误代码是：

public void insert(E e) {
    Node<E> newNode = new Node<>(e);

    if (root == null) {
        root = newNode;
    } else {
        Node<E> current = root;
        Node<E> parent = null;

        while (true) {
            parent = current;
            if (e.compareTo(current.element) < 0) // missing { ...
                current = current.left; // ... so only this is in the if block

            if (current == null) {
                parent.left = newNode;
                return;
            } else { // oops, this should be else to the e.compareTo(current.element) < 0 condition
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }
}

---

修复了代码（假设允许重复）：

public void insert(E e) {
    Node<E> newNode = new Node<>(e);

    if (root == null) {
        root = newNode;
    } else {
        Node<E> current = root;
        Node<E> parent = null;

        while (true) {
            parent = current;
            if (e.compareTo(current.element) < 0) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }
}

---

这个故事的寓意是：保持代码格式良好，并在代码块上使用大括号，这样可以省去你的麻烦