java - 尝试打印时二分查找树的指针问题

Question

我正在编写按顺序打印二叉搜索树的方法。我找到了一种方法来做到这一点，但它需要在打印节点时删除或使节点无效。下面是我的代码:

public String printKeysInOrder() {
        String output = "";
        if (isEmpty()) return "()";
        else{
            int i = 0;
            while(i!=size()){
                Node x = root;
                int loopBreak = 0;
                while(loopBreak!=1){
                    if(x.left != null) x = x.left;
                    else if (x.right != null){
                        output = output + " " + x.val;
                        x.key = null;
                        x = x.right;
                        i++;
                    }
                    else{
                        output = output + " " + x.val;
                        x.key = null;
                        loopBreak = 1;
                    }
                }
                i++;
            }
        }
        return output;
    }

对于树:

            _7_
          /     \
        _3_      8
      /     \
     1       6
      \     /
       2   4
            \
             5

它应该打印“1 2 3 4 5 6 7 8”

代码的工作方式是它倾向于在树中向左移动，直到它不能再向左移动为止，然后它将该节点的值存储在字符串输出中，使节点键等于 null(因此 future 的迭代循环不会沿着该树向下移动)并在可能的情况下向右移动或围绕循环迭代回来。

尽管我在使节点等于 null 时遇到了麻烦，因为当执行代码时(通过 junit 测试)，代码无法识别该 null 键并无论如何都会遍历该子树？任何人都可以帮助我或告诉我如何制作它，以便 future 迭代中的 x.left 和 x.right 指针将节点识别为空吗？

Answer 1

您不需要取消或删除节点，您需要遍历算法。

此处提供的有序遍历无需进行重大修改即可工作: http://www.javabeat.net/binary-search-tree-traversal-java/

另一种面向对象的方法是提供一个可按顺序遍历的访问者，它允许您提供在每个节点执行的操作，无论是打印、收集、映射还是其他操作。