如何显示从最低点开始旋转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

输出：

P.S 我尝试了 How to print binary tree diagram in Java 中的信息，但无法解决问题:(

Answer 1

一些观察：

如果你想让节点出现在正确的位置，你必须在你的递归函数中使用in-order遍历：向左下降，然后打印，然后向右下降。
每个节点没有常量前缀。在你的第二个例子中，当你从 76 向左走时，你必须打印 76 和 45 之间的连接，但是如果向右走，则没有相同深度的连接。

您可以通过保存方向历史记录来解决这个问题，例如作为 L 和 R 的字符串。
每个节点都有一个“postfix”，这取决于它是左还是右 child 还是两者都有。
数字必须填充到固定宽度，以便“后缀”与连接对齐。

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

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]) ? "     "
                                                   : "    │";
            }
            
            prefix += (path[path.length - 1] == "L") ? "    ┌"
                                                     : "    └";
        }

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

        let postfix = " ┘┐┤"[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 从不调用 TreeNode class
上的 print 方法
TreeNode class 上的 print 方法按预序访问节点。对于中序，你应该先访问左子树，然后是节点本身，然后是右子树

这里是对 TreeNode 中 print 方法的更正：

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:

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

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

How to display binary search tree rotated 90deg which starts from lowest point

java

algorithm

data-structures

printing

binary-search-tree