java - 不使用集合类的二叉搜索树迭代器实现

Question

我无法弄清楚如何实现二分搜索迭代器。我的问题是如何在不使用集合类的情况下实现“按顺序”遍历的迭代器？

嗯，问题是我不知道如何添加“parent”，因为我在迭代器中找到前 4 个项目，但我似乎无法上升，因为“parent”要么抛出空指针或没有得到正确的项目。

那么如何添加“parent”呢？

    void add(String string) {
    if (string.compareTo(value) < 0) {
            if(left.left == null){
                left.parent = left;
            }
            if (left == null) {
                size++;

                left = new Node(string);
            if...

谢谢。

Answer 1

我建议采用三类设计:

• BinarySearchTree:公共(public)类，代表二叉搜索树。它包含作为 BinaryTreeNode 的树根。
• BinaryTreeNode:私有(private)嵌套类，它代表一个节点，它具有键和引用:对子节点和对父节点的引用。

• BinarySearchTreeIterator:私有(private)嵌套类，它代表一个迭代器，它使用对 BinaryTreeNode 的引用来了解当前元素。

  public class BinarySearchTree implements Iterable<String> {
  
      private BinaryTreeNode root = null;
      private int elements;
  
      @Override
      public Iterator<String> iterator() {
          return new BinarySearchTreeIterator(root);
      }
  
      private static class BinarySearchTreeIterator implements Iterator<String> {
  
          private BinaryTreeNode node;
  
          public BinarySearchTreeIterator(BinaryTreeNode node) {
              if (node != null) {
                  this.node = smallest(node);
              } else {
                  this.node = node;
              }
          }
  
          @Override
          public boolean hasNext() {
              return node != null;
          }
  
          private static BinaryTreeNode smallest(BinaryTreeNode n) {
              if (n.left != null) {
                  return smallest(n.left);
              } else {
                  return n;
              }
          }
  
          @Override
          public String next() {
              String result = node.key;
              if (node.right != null) {
                  node = smallest(node.right);
              } else {
                  while (node.parent != null && node.parent.left != node) {
                      node = node.parent;
                  }
                  node = node.parent;
              }
              return result;
          }
      }
  
      private static class BinaryTreeNode {
  
          private String key;
          private BinaryTreeNode parent;
          private BinaryTreeNode left;
          private BinaryTreeNode right;
  
          public BinaryTreeNode(String key) {
              this.key = key;
          }
      }
  
      public boolean insert(String key) {
          if (key == null) {
              return false;
          }
          int lastElements = elements;
          this.root = insert(key, root, null);
          return lastElements < elements;
      }
  
      private BinaryTreeNode insert(String key, BinaryTreeNode node, BinaryTreeNode parent) {
          BinaryTreeNode result = node;
          if (node == null) {
              result = new BinaryTreeNode(key);
              result.parent = parent;
              this.elements++;
          } else {
              int compare = key.compareTo(node.key);
              if (compare < 0) {
                  result.left = insert(key, node.left, node);
              } else if (compare > 0) {
                  result.right = insert(key, node.right, node);
              }
          }
          return result;
      }
  
      public static void main(String[] args) {
          BinarySearchTree tree = new BinarySearchTree();
          String[] strings = {"l", "f", "t", "c", "g", "p", "u"};
          for (String string : strings) {
              System.out.println("insert: '" + string + "' " + tree.insert(string));
          }
          System.out.println("--");
  
          for (String s : tree) {
              System.out.println(s);
          }
      }
  }
  

它打印:

insert: 'l' true
insert: 'f' true
insert: 't' true
insert: 'c' true
insert: 'g' true
insert: 'p' true
insert: 'u' true
--
c
f
g
l
p
t
u