java - 如何显示从最低点开始旋转 90 度的二叉搜索树

Question

我创建了一个二叉搜索树，如下所示：

static class TreeNode{
    private int data;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int data){
        this.data=data;
    }

    public void add(int data){
        if( data >= this.data){
            if(this.rightChild == null){
                this.rightChild = new TreeNode(data);
            }else{
                this.rightChild.add(data);
            }
        }else {
            if(this.leftChild == null){
                this.leftChild = new TreeNode(data);
            }else {
                this.leftChild.add(data);
            }
        }
    }

    public int getData(){
        return data;
    }
    public  void setLeftChild(TreeNode leftChild){
        this.leftChild = leftChild;
    }
    public  void setRightChild(TreeNode rightChild){
        this.rightChild = rightChild;
    }
    public TreeNode getLeftChild(){
        return leftChild;
    }
    public TreeNode getRightChild(){
        return rightChild;
    }
    public void print() {
        print("", this, false);
    }

    public void print(String prefix, TreeNode n, boolean isLeft) {
        if (n != null) {
            System.out.println (prefix + (isLeft ? "|-- " : "\\-- ") + n.data);
            print(prefix + (isLeft ? "|   " : "    "), n.leftChild, true);
            print(prefix + (isLeft ? "|   " : "    "), n.rightChild, false);
        }
    }
}

static class BinaryTree{

  private TreeNode root;

  public void pprint(){
      traversePreOrder(this.root);
  }

  public void traversePreOrder(TreeNode node) {
      if (node != null) {
          System.out.print(" " + node.data);
          traversePreOrder(node.leftChild);
          traversePreOrder(node.rightChild);
      }
  }
}

我想显示我的树，但不是正常显示，而是从最低点开始旋转 90 度。

例如：如果输入是：901 292 247 997 457 468 216 82 530 524 793 952 730 764 820 460 424

输出应如下所示：

另一个例子：如果输入是：302 946 638 376 604 610 45 547 76 347 694 495 51 130 159

输出：

PS我尝试了如何在Java中打印二叉树图中的信息，但我无法解决问题:(

Answer 1

一些观察：

• 如果您希望节点显示在正确的位置，则必须在递归函数中使用按顺序遍历：向左下降，然后打印，然后向右下降。

• 每个节点没有固定的前缀。在您的第二个示例中，当您从 76 向左走时，您必须打印 76 和 45 之间的连接，但如果您向右走，则在相同深度处没有连接。

  您可以通过保存方向的历史来解决这个问题，例如作为 L's 和 R's 的字符串。

• 每个节点都有一个“后缀”，这取决于它是否有左孩子或右孩子或两者兼而有之。

• 数字必须填充到固定宽度，以便“后缀”与连接对齐。

我不会说 Java，但这里有一些类似 Javascript 的伪代码，可以实现你想要的：

function tree_print(n, path) {
    if (n) {
        // determine prefix

        let prefix = "";

        if (path.length > 0) {
            for (let i = 1; i < path.length; i++) {
                prefix += (path[i] == path[i - 1]) ? "     "
                                                   : "    │&quot;;
            }
            
            prefix += (path[path.length - 1] == "L") ? "    ┌&quot;
                                                     : "    └&quot;;
        }

        // determine postfix
        
        let post = 0;
        if (n.left) post |= 1;
        if (n.right) post |= 2;

        let postfix = " ┘┐┤&quot;[post];
    
        tree_print(n.left, path + "L");
        print(prefix + pad(n.value) + postfix);
        tree_print(n.right, path + "R");
    } 
}

调用它（假设）：

tree_print(root, "");

Answer 2

一些问题：

• this当您已经拥有当前 ( ) 实例时，您不需要将节点实例作为参数传递。

• pprint从不调用类print上的方法TreeNode

• 类上的print方法按TreeNode顺序访问节点。对于有序，您应该首先访问左子树，然后是节点本身，然后是右子树

print以下是对中方法的更正TreeNode：

class TreeNode{

    /* ... constructor and other methods here ... */

    public void print() {
        print("", "", "", "");
    }

    public void print(String prefix, String left, String mid, String right) {
        String indent = " ".repeat(String.valueOf(data).length());
        if (leftChild != null) {
            leftChild.print(prefix + left + indent, " ", "┌", "│");
        }
        System.out.println(prefix + mid + data 
                           + " ┐┘┤".charAt((leftChild  != null ? 2 : 0) 
                                         + (rightChild != null ? 1 : 0)));
        if (rightChild != null) {
            rightChild.print(prefix + right + indent, "│", "└", " ");
        }
    }
}

在BinaryTree我们将简单地将工作推迟到TreeNode班级：

class BinaryTree {
    private TreeNode root;

    public void pprint() {
        if (root != null) {
            root.print();
        }
    }

    public void add(int data) {
        if (root == null) {
            root = new TreeNode(data);
        } else {
            root.add(data);
        }
    }
}