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

Question

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

插入整数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;
  }
}

BinarySearchTree.class:

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 block 中的结果:

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;
                }
            }
        }
    }
}

<小时/>

这个故事的寓意:保持代码格式正确并在 block 中使用大括号将为您省去麻烦。